Constrained Submodular Set Function Maximization

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!

Recently Viewed Presentations

  • ENGLISH GRAMMAR EXERCISES LOGISTICS Simple Past Tenses [-ed]-

    ENGLISH GRAMMAR EXERCISES LOGISTICS Simple Past Tenses [-ed]-

    SIMPLE vs Complex Sentences Connecting Words and , but although, despite of , despite the fact that, which, nevertheless, , when, though, because. A. We need to increase the quality of our research. Increasing the quality of our research will...
  • Frontiers to Wonder and Discovery

    Frontiers to Wonder and Discovery

    Mobile Instructional Laboratory Experiments and Their Use in Computing Sciences St. Joseph's College Bert G. Wachsmuth Seton Hall University CCSCE 2007 Bert Wachsmuth, Seton Hall * * * * * * * * * * * * * * *...
  • innovis.cpsc.ucalgary.ca

    innovis.cpsc.ucalgary.ca

    University of British Columbia Vancouver, BC, Canada [email protected] Sheelagh Carpendale Dept. of Computer Science University of Calgary Calgary, AB, Canada [email protected] A Study of the Information Analysis Process (With Paper!) 1. Browse 2. Parse 3. Discuss Collaboration Style 4. Establish...
  • College of Social Sciences Research 2018 v0.8 Craig

    College of Social Sciences Research 2018 v0.8 Craig

    fiona d. angela. adam smith busness school accounting & finance. x economics x. management x school of education x. school of interdisciplinary studies. x school of law x school of social & political sciences central & east european studies x....
  • MWDS - Leon County Schools

    MWDS - Leon County Schools

    Definition: a main idea or an underlying meaning of a literary work that may be stated directly or indirectly. **Avoid confusing THEME with a SUBJECT. Subject is a topic which acts as a foundation for a literary work, while a...
  • Checking Out Me History John Agard What is

    Checking Out Me History John Agard What is

    This poem makes the reader question the way in which history is taught and how we, the reader, conceive our own identity as we learn about other cultures and races other than our own, as he uses the poem to...
  • Earth, Moon and Sun

    Earth, Moon and Sun

    Earth, Moon and Sun. Lunar Eclipse. Lunar eclipses only occur during the . Full Moon phase. A total lunar eclipse is sometimes referred to as a "blood moon" next Jan. 20, 2019. A lunar eclipse occurs when the Earth passes...
  • Do well by doing good Katerina Jovanovska, 20.04.2014,

    Do well by doing good Katerina Jovanovska, 20.04.2014,

    Models of market capitalism. LME-coordinate economic activity through markets and corporate hierarchies and compete successfully on the basis of low costs and major product and technological innovations;CME- coordinate economic activity more through non-market mechanisms, such as informal networks or corporatist...