On approximating (sparse) covering integer programs

Research output: Contribution to conferencePaper

Abstract

We consider approximation algorithms for covering integer programs of the form min hc, xi over x ∈ Zn0 s.t. Ax ≥ b and x ≤ d; where A ∈ Rm0×n, b ∈ Rm0, and c, d ∈ Rn0 all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x ≤ d as CIP. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP.

Original languageEnglish (US)
Pages1596-1615
Number of pages20
StatePublished - Jan 1 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019

Conference

Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
CountryUnited States
CitySan Diego
Period1/6/191/9/19

Fingerprint

Integer Program
Covering
Approximation Algorithms
Approximation algorithms
Linear Time
Randomized Rounding
LP Relaxation
Set Cover
Covering Problem
Algorithm Analysis
Knapsack
Knapsack Problem
Resampling
Randomized Algorithms
Approximation
Approximation Scheme
Best Approximation
Fast Algorithm
Simplicity
Multiplicative

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Chekuri, C. S., & Quanrud, K. (2019). On approximating (sparse) covering integer programs. 1596-1615. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.

On approximating (sparse) covering integer programs. / Chekuri, Chandra Sekhar; Quanrud, Kent.

2019. 1596-1615 Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.

Research output: Contribution to conferencePaper

Chekuri, CS & Quanrud, K 2019, 'On approximating (sparse) covering integer programs', Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States, 1/6/19 - 1/9/19 pp. 1596-1615.
Chekuri CS, Quanrud K. On approximating (sparse) covering integer programs. 2019. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.
Chekuri, Chandra Sekhar ; Quanrud, Kent. / On approximating (sparse) covering integer programs. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.20 p.
@conference{a3accf78edd34c80b6c74ed406f9a798,
title = "On approximating (sparse) covering integer programs",
abstract = "We consider approximation algorithms for covering integer programs of the form min hc, xi over x ∈ Zn≥0 s.t. Ax ≥ b and x ≤ d; where A ∈ Rm≥0×n, b ∈ Rm≥0, and c, d ∈ Rn≥0 all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x ≤ d as CIP∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP∞.",
author = "Chekuri, {Chandra Sekhar} and Kent Quanrud",
year = "2019",
month = "1",
day = "1",
language = "English (US)",
pages = "1596--1615",
note = "30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 ; Conference date: 06-01-2019 Through 09-01-2019",

}

TY - CONF

T1 - On approximating (sparse) covering integer programs

AU - Chekuri, Chandra Sekhar

AU - Quanrud, Kent

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We consider approximation algorithms for covering integer programs of the form min hc, xi over x ∈ Zn≥0 s.t. Ax ≥ b and x ≤ d; where A ∈ Rm≥0×n, b ∈ Rm≥0, and c, d ∈ Rn≥0 all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x ≤ d as CIP∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP∞.

AB - We consider approximation algorithms for covering integer programs of the form min hc, xi over x ∈ Zn≥0 s.t. Ax ≥ b and x ≤ d; where A ∈ Rm≥0×n, b ∈ Rm≥0, and c, d ∈ Rn≥0 all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x ≤ d as CIP∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP∞.

UR - http://www.scopus.com/inward/record.url?scp=85065888064&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065888064&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85065888064

SP - 1596

EP - 1615

ER -