Constrained Submodular Set Function Maximization

On Approximating Covering Integer Programs Chandra Chekuri Univ. of Illinois, Urbana-Champaign Joint work with Kent Quanrud Workshop on Flexible Network Design, May 2018 Set Cover U = {1, 2, , m} Sets S1, S2, , Sn each a subset of U

ci : non-negative cost of Si Goal: Find min-cost sub-collection of S1, S2, , Sn whose union is U Parameters: m, n, N = size of instance : max set size, : max frequency over elements Approximating Set Cover Greedy algorithm: H 1 + ln 1 + ln m [Johnson74, Stein74, Lovasz75, Chavtal79] LP rounding:

[Hochbaum82] O(log m) [Raghavan-Thompson87] O(log ) [Srinivasan96,01,06,] [Saket-Sviridenko12] Unweighted, special cases, many results .

Hardness of Approximation No (1- ) ln m approx. unless P = NP [Moshkovitz15, Feige98] No ln - ln ln approx. unless P = NP [Trevisan01] No ( - ) approx. under UGC [Bansal-Khot10] No ( 1 - ) approx. unless P = NP [Dinur et

al03] Covering Integer Programs min + , +

, + , +

CIP : with multiplicity constraints CIP : without multiplicity constraints, dj = Normalization and Parameters min

[ 0,1 ] , 1, + , + 0 max # of non-zeroes in a column 1 max column sum 0 max # of non-zeroes in a row 1 max row sum

Under normalization 1 0 and 1 Approximating CIPs Greedy algorithm: H* 1 + ln * where * is max column sum when A is normalized to integers. Can be as large as m [Dobson82,

Wolsey] LP rounding: O(log m) for CIP [Raghavan-Thompson] O(log ) for CIP [Srinivasan99] O(log ) for CIP using Knapsack-Cover inequalities [Kolliopoulos-Young00] [Chen-Harris-Srinivasan16] tight bounds Knapsack Cover Inequalities Basic-LP has large integrality gap for CIP [Carr-Fleischer-Leung-Phillips00] KCinequalities

min min , =max { 0, , } 0 ,, =

\{ , , , } { Approximating CIPs Focus of this talk: , are some fixed constant C [Chen-Harris-Srinivasan16] CIP: via KC-LP CIP : [1 + via Basic-LP

Bicriteria for CIP: output with cost approx. via BasicLP Resampling framework following constructive versions of LLL [Moser-Tardos and others including HarrisSrinivasan ] 1 bound 1 can be much smaller than 0

More robust to noise in data Technically interesting Our Results 1. Fast approximation scheme for solving KCLP 2. Simple and (slightly) improved approximations for CIP and CIP based on round+fix framework 3. Easy derandomization of algorithms: first deterministic algorithms with near-tight bounds

Solving KC-LP [Carr etal] Ellipsoid method via separation oracle for Knapsack Cover. MWU based approximation scheme. (1+))approximation in O(nN log C poly(1/)) ))) time Our result: O(N log C poly(1/)) ))) time. Nearlinear if C is poly-bounded Approximation Bounds [Chen-HarrisSrinivasan16]

New CIP: KC-LP CIP : [1+ ] Basic-LP [

CIP: output cost approx via Basic-LP via KC-LP Row sparsity: (1+ 0) for CIP and (1 + 1) for CIP : tight Focus of this talk: , are some fixed constant C

Round+Fix Algorithm [Srinivasan01,Saket-Sviridenko12,Gupta-Nagarajan16] 1. Solve LP relaxation: x fractional solution 2. Pick parameter 1 and randomly and independently set zj to or s.t 3. For each unsatisfied constraint i (ie do y(i) is solution to knapsack cover problem induced by constraint i

4. Output z Round+Fix Algorithm for CIP 1. Solve KC-LP relaxation: x fractional solution 2. Pick parameter 1. If set zj to dj Else randomly and independently set zj to or s.t 3. For each unsatisfied constraint i (ie do

y(i) is solution to knapsack cover problem induced by constraint i 4. Output z Knapsack Cover CIP with m = 1 (single covering constraint) KC-LP integrality gap is 2 [Carr et al] Basic LP: given x, there is is integer solution z s.t and and .

FPTAS via DP High-level Analysis of Round+Fix Output is feasible solution by construction Expected cost? pi : probability that i not covered Only tool: Chernoff Bound X1, X2, , Xn independent random variables in [0,1]

If X1, X2, , Xn in [0,]] CIP: Ax 1, x 0 Round+Fix algorithm, choose pi = Pr[ (Az)i < 1 ] exp(1 + ln ) 1/)) (20) Expected cost: Hence ( + 1) LP-Cost

CIP: Ax 1, x d, x 0 Round+Fix algorithm, choose Same analysis gives + 1 approx. wrt KC-LP CIP: Ax 1, x 0, 1 bound Round+Fix algorithm, choose Claim: Expected cost is ( + O(1)) LP-Cost Proof a bit clever but still relies only on

Chernoff bound 1 bound: intuition Understand pi which can be non-uniform Suppose Ai,j ] for all j then pi = Pr[ (Az)i < 1 ] exp((1 + ln )/)) ]) ]/)) (21) 1 bound: intuition Suppose Ai,j = ] or 0 for all j then

pi = Pr[ (Az)i < 1 ] exp((1 + ln )/)) ]) ]/)) (21) 1 bound: general case Constraint i: There exists i such that and Pr[ (Az)i < 1 ] exp((1 /)) 2 + ln /)) 2)/)) i) O(i/)) 1) 1 bound: general case

and Pr[ (Az)i < 1 ] exp((1 /)) 2 + ln /)) 2)/)) i) O(i/)) 1) Expected cost: Hence expected cost is ( + O(1)) LP-Cost Derandomization Algorithm is simple. Feasibility guaranteed, only cost is random. Analysis relies only on simple Chernoff bound Use method of conditional expectations via

Chernoff bound derivation-formula as pessimistic estimator Easy and efficient deterministic algorithm Conclusions Fast (near-linear) approximation scheme to solve KC-LP Randomized rounding + fixing appears to be a universal algorithm for Set Cover and CIPs: for each scenario different parameter . Algorithm: try all values of and take the best. Oblivious to parameters and may work

better in practice. Derandomization Thank You!