TY - GEN
T1 - 1-sparsity Approximation Bounds for Packing Integer Programs
AU - Chekuri, Chandra
AU - Quanrud, Kent
AU - Torres, Manuel R.
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - We consider approximation algorithms for packing integer programs (PIPs) of the form where c, A, and b are nonnegative. We let denote the width of A which is at least 1. Previous work by Bansal et al. [1] obtained an -approximation ratio where is the maximum number of nonzeroes in any column of A (in other words the -column sparsity of A). They raised the question of obtaining approximation ratios based on the -column sparsity of A (denoted by) which can be much smaller than Motivated by recent work on covering integer programs (CIPs) [4, 7] we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. [1] (but with a twist), yield approximation ratios for PIPs based on First, following an integrality gap example from [1], we observe that the case of is as hard as maximum independent set even when In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width where we obtain an -approximation. In the large width regime, when we obtain an -approximation. We also obtain a -approximation when.
AB - We consider approximation algorithms for packing integer programs (PIPs) of the form where c, A, and b are nonnegative. We let denote the width of A which is at least 1. Previous work by Bansal et al. [1] obtained an -approximation ratio where is the maximum number of nonzeroes in any column of A (in other words the -column sparsity of A). They raised the question of obtaining approximation ratios based on the -column sparsity of A (denoted by) which can be much smaller than Motivated by recent work on covering integer programs (CIPs) [4, 7] we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. [1] (but with a twist), yield approximation ratios for PIPs based on First, following an integrality gap example from [1], we observe that the case of is as hard as maximum independent set even when In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width where we obtain an -approximation. In the large width regime, when we obtain an -approximation. We also obtain a -approximation when.
KW - Approximation algorithms
KW - Packing integer programs
KW - column sparsity
UR - http://www.scopus.com/inward/record.url?scp=85065881347&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85065881347&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-17953-3_10
DO - 10.1007/978-3-030-17953-3_10
M3 - Conference contribution
AN - SCOPUS:85065881347
SN - 9783030179526
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 128
EP - 140
BT - Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
A2 - Lodi, Andrea
A2 - Nagarajan, Viswanath
PB - Springer
T2 - 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Y2 - 22 May 2019 through 24 May 2019
ER -