1-sparsity Approximation Bounds for Packing Integer Programs

Chandra Sekhar Chekuri, Kent Quanrud, Manuel R. Torres

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
EditorsAndrea Lodi, Viswanath Nagarajan
PublisherSpringer-Verlag
Pages128-140
Number of pages13
ISBN (Print)9783030179526
DOIs
StatePublished - Jan 1 2019
Event20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States
Duration: May 22 2019May 24 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11480 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
CountryUnited States
CityAnn Arbor
Period5/22/195/24/19

Fingerprint

Integer Program
Sparsity
Packing
Approximation
Approximation algorithms
Randomized Rounding
LP Relaxation
Maximum Independent Set
Integrality
Twist
Approximation Algorithms
Covering
Strictly
Non-negative
Denote

Keywords

  • Approximation algorithms
  • Packing integer programs
  • column sparsity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Chekuri, C. S., Quanrud, K., & Torres, M. R. (2019). 1-sparsity Approximation Bounds for Packing Integer Programs. In A. Lodi, & V. Nagarajan (Eds.), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings (pp. 128-140). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-030-17953-3_10

1-sparsity Approximation Bounds for Packing Integer Programs. / Chekuri, Chandra Sekhar; Quanrud, Kent; Torres, Manuel R.

Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. ed. / Andrea Lodi; Viswanath Nagarajan. Springer-Verlag, 2019. p. 128-140 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chekuri, CS, Quanrud, K & Torres, MR 2019, 1-sparsity Approximation Bounds for Packing Integer Programs. in A Lodi & V Nagarajan (eds), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11480 LNCS, Springer-Verlag, pp. 128-140, 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019, Ann Arbor, United States, 5/22/19. https://doi.org/10.1007/978-3-030-17953-3_10
Chekuri CS, Quanrud K, Torres MR. 1-sparsity Approximation Bounds for Packing Integer Programs. In Lodi A, Nagarajan V, editors, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Springer-Verlag. 2019. p. 128-140. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-17953-3_10
Chekuri, Chandra Sekhar ; Quanrud, Kent ; Torres, Manuel R. / 1-sparsity Approximation Bounds for Packing Integer Programs. Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. editor / Andrea Lodi ; Viswanath Nagarajan. Springer-Verlag, 2019. pp. 128-140 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{1a56739662d04908acbf0d848710aeca,
title = "1-sparsity Approximation Bounds for Packing Integer Programs",
abstract = "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.",
keywords = "Approximation algorithms, Packing integer programs, column sparsity",
author = "Chekuri, {Chandra Sekhar} and Kent Quanrud and Torres, {Manuel R.}",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-030-17953-3_10",
language = "English (US)",
isbn = "9783030179526",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "128--140",
editor = "Andrea Lodi and Viswanath Nagarajan",
booktitle = "Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings",

}

TY - GEN

T1 - 1-sparsity Approximation Bounds for Packing Integer Programs

AU - Chekuri, Chandra Sekhar

AU - Quanrud, Kent

AU - Torres, Manuel R.

PY - 2019/1/1

Y1 - 2019/1/1

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

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-Verlag

ER -