
Chain-Constrained Spanning Trees: Approximation Algorithms and Constrained MST Problems
Explore approximation algorithms for minimizing costs in chain-constrained spanning trees, delving into constrained MST problems with a focus on degree constraints. Learn about the challenges, previous algorithms, and the search for efficient solutions within these constraints.
Download Presentation

Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Approximation Algorithms for Min-cost Chain-Constrained Spanning Trees Chaitanya Swamy University of Waterloo Joint work with Andre Linhares University of Waterloo
RECALL: MST problem G=(V,E) n=|V|, m=|E| edge costs {ce 0} c(T) MST problem: find spanning tree T to minimize e T ce
RECALL: MST problem G=(V,E) n=|V|, m=|E| edge costs {ce 0} c(T) MST problem: find spanning tree T to minimize e T ce Well-understood: various polynomial time algorithms, nice polyhedral characterization Interested in constrained MST problems: find a min-cost spanning tree satisfying additional packing constraints
Constrained MST problems Will focus on degree constraints (in various flavors) Min {c(T): T is spanning tree, degT(v) bv for all v} Degree-bounded MST: NP-hard to satisfy degree-bounds exactly Can efficiently deduce infeasibility OR find T with c(T) OPT, AND (Goemans06) degT(v) bv+2 v (Singh-Lau07) degT(v) bv+1 v (LP rounding using matroid inters n.) (iterative rounding+ relaxation) Good understanding of how to handle node-degree constraints no. of edges of T crossing S V collection of node-sets More generally, what about degree constraints on cuts? Min {c(T): T is spanning tree, degT(S) bS for all S This is the kind of problem that crops up in finding thin trees ( =2V)
Constrained MST (contd.) finds T with c(T) = O(OPT) AND degT(S) = O(bS) S (for any C where edges participate in non-constant # of degree constraints) Our result: Give an algorithm providing the above guarantees when C is a chain No known algorithm that: if problem is feasible, What about degree constraints on cuts? Min {c(T): T is spanning tree, degT(S) bS for all S Very limited understanding: don t know how to effectively leverage techniques used to handle node-degrees Can determine infeasibility OR find T with c(T) OPT, AND (BKN08) degT(S) bS+r-1 S (CVZ10, AGMOS10) degT(S) min{O()bS , (1+ )bS + O( )} (BKKNP10) degT(S) bS +O(log n) S if is laminar r=maxe (# of degree constr. containing e) log |C| log log |C| log |C| S S, T , S T= or S T or T S If is a nested collection of sets (chain), then (OZ13) show: one can determine infeasibility OR find T with degT(S) = O(bS) S BUT: there is no bound on c(T)
Chain-constrained spanning trees S3 S4 S2 G=(V,E), edge costs {ce} Nested family (chain) of sets : S1 S2 Sk S1
Chain-constrained spanning trees S3 S4 S2 G=(V,E), edge costs {ce} Nested family (chain) of sets : S1 S2 Sk Degree bounds {bS }S S1 1 1 2 2 Chain-constrained spanning tree problem: Min {c(T): T spanning tree, degT(S) bS for all S }
Chain-constrained spanning trees S3 S4 S2 G=(V,E), edge costs {ce} Nested family (chain) of sets : S1 S2 Sk Degree bounds {bS }S S1 1 1 2 2 Chain-constrained spanning tree problem: Min {c(T): T spanning tree, degT(S) bS for all S } Our result: Polytime algorithm that detects infeasibility OR returns T with c(T)=O(OPT) AND degT(S)=O(bS) S an (O(1), O(1))-approximation
Our results Devise (O(1), O(1))-approximation algorithm for min- cost chain-constrained spanning tree (CCST) cost approximation degree-bound violation First algorithm to give O(1) approx. to BOTH cost and degrees (OZ13: c s.t. NP-hard to obtain additive c. log n log log n -approx.) Use Lagrangian-relaxation in a novel way to simplify cost structure and obtain collection of unweighted problems Technique applicable to a larger class of problems
Our results (contd.) Consider the following general problem: Min cTx s.t. x is an extreme point of P, Ax b Generalizes min-cost chain-constrained spanning tree P: spanning-tree polytope, Ax b: degree constraints We show that, under certain assumptions: O(1)-approx. for unweighted (QP) returns extreme point x of P s.t. Ax O(1)b (no bound on cTx) (QP) (O(1), O(1))-approx. for (QP) (1, O(1))-approx. for (QP) Two-sided O(1)-approx. for unweighted (QP)
Our results (contd.) Consider the following general problem: Min cTx s.t. x is an extreme point of P, Ax b We show that, under certain assumptions: O(1)-approx. for unweighted (QP) Two-sided O(1)-approx. for unweighted (QP) Application to k-budgeted matroid basis: Obtain randomized nO(k1.5/ )-time (1,1+ , ,1+ )-approx. using randomized algorithm of (BN15) Get both improved approx. guarantee of (GRSZ14), and improved running time of (BN15) (QP) (O(1), O(1))-approx. for (QP) (1, O(1))-approx. for (QP)
LP-relaxation for min-cost CCST (S) = boundary of set S={(u,v) E: exactly one of u,v is in S} E(S) = edges with both ends in S={(u,v) E: both u,v are in S} xe : indicates if edge e lies in the spanning tree For F E, use x(F) to denote e F xe Minimize e ce xe subject to, x(E(S)) |S|-1 x(E) = n-1 x 0 x( (S)) bS (P) for all S V (*) for all S . Can efficiently compute optimal solution x* to (P) Let OPT = optimal value of (P) Call a vector x satisfying (*), a fractional spanning tree
Rounding algorithm ingredients Tight spanning tree constraints Let L = maximal laminar family of sets from {S: x*(E(S))=|S|-1} So L contains E, singletons {v} for all v V (Will always use L to denote set in L, S to denote set in ) Assume E is support of x* L sets in L Let GL =(V, EL) be graph obtained from (L, E(L)) by contracting children of L
Rounding algorithm ingredients Tight spanning tree constraints Let L = maximal laminar family of sets from {S: x*(E(S))=|S|-1} So L contains E, singletons {v} for all v V (Will always use L to denote set in L, S to denote set in ) Assume E is support of x* L sets in L children of L Let GL =(V, EL) be graph obtained from (L, E(L)) by contracting children of L
Rounding algorithm ingredients Tight spanning tree constraints Let L = maximal laminar family of sets from {S: x*(E(S))=|S|-1} So L contains E, singletons {v} for all v V (Will always use L to denote set in L, S to denote set in ) Assume E is support of x* L sets in L children of L Let GL =(V, EL) be graph obtained from (L, E(L)) by contracting children of L For all L, x*L := (x*e)e EL is a fractional spanning tree of GL Build spanning tree of G by combining spanning trees of all GL s
Rounding algorithm ingredients Let L = maximal laminar family of sets from {S: x*(E(S))=|S|-1} sets in L children of L L Let GL =(V, EL) be graph obtained from (L, E(L)) by contracting children of L For all L, x*L := (x*e)e EL is a fractional spanning tree of GL Build spanning tree of G by combining spanning trees of GL s Theorem (OZ13): For every L, can find spanning tree TL of GL s.t. if T = combination of TL s, then degT(S) = O(x*( (S))) S . Based on modifying x*L to satisfy certain property (rainbow-freeness) Can cost of fractional tree arbitrarily, unless we have uniform costs
Rounding algorithm ingredients Let L = maximal laminar family of sets from {S: x*(E(S))=|S|-1} sets in L children of L L Let GL =(V, EL) be graph obtained from (L, E(L)) by contracting children of L Theorem (OZ13): For every L, can find spanning tree TL of GL s.t. if T = combination of TL s, then degT(S) = O(x*( (S))) S . Observation: OZ13 gives low-cost tree if, for all L, all edges in EL have equal cost (weaker than: all edges in E have equal costs) Key insight: Can equalize costs in EL by perturbing costs using optimal values of dual vars. corresponding to degree constr. But this also seems rather special !
Equalizing costs in EL Minimize e ce xe subject to, x(E(S)) |S|-1 x(E) = n-1 x 0 x( (S)) bS (P) for all S V (ST) y*S 0: opt. value of dual variable for all S . Define cy*e = ce + S C: e (S) y*S Key Lemma: For all L L, for all e,f EL, we have cy*e = cy*f Proof: By complementary slackness, ce = (Dual contribution to e from (ST)) S C: e (S) y*S cf = (Dual contribution to f from (ST)) S C: f (S) y*S But e, f belong to same sets of laminar family L incur same dual contribution from spanning tree constraints, so cy*e = cy*f .
Putting everything together Algorithm (almost) 1. Solve (P) and its dual to get x* and (y*S) S C . 2. Define laminar family L, use OZ13 to find spanning tree TL of GL for each L L; return T = combination of TL s. Analysis: By OZ13, have degT(S) = O(x*( (S)) = O(bS) Define cy*e = ce + S C: e (S) y*S for all e in support(x*). For every L, all edges in EL have same cy*-cost, so cy*(TL) = e EL cy*e x*e c(T) cy*(T) = e E cy*e x*e= OPT + S CbSy*S Problem: S CbSy*S may be >> OPT Fix: Start with slightly inflated degree bounds (e.g., 2bS)
Putting everything together with degree bounds (2bS)S C Algorithm (almost) 1. Solve (P) and its dual to get x* and (y*S) S C . 2. Define laminar family L, use OZ13 to find spanning tree TL of GL for each L L; return T = combination of TL s. Analysis: By OZ13, have degT(S) = O(x*( (S)) = O(bS) O(2bS) Define cy*e = ce + S C: e (S) y*S for all e in support(x*). For every L, all edges in EL have same cy*-cost, so cy*(TL) = e EL cy*e x*e c(T) cy*(T) = e E cy*e x*e = e E ce x*e +2 S CbSy*S Problem: S CbSy*S may be >> OPT Fix: Start with slightly inflated degree bounds (e.g., 2bS) OPT 2.OPT
General reduction from weighted to unweighted problems x is an extreme point of P, Ax b (QP) Min cTx How can we use an O(1)-approximation for unweighted (QP) to obtain approximation guarantees for (QP)? Key properties we utilize from OZ13-algorithm: approximation for unweighted problem preserves tight spanning-tree constraints Face-preserving rounding algorithm (FPRA): rounds x P to an extreme point x s.t. minimal face of P containing x -approximation FPRA: also A x b (no guarantee on cost) s.t. x x x
Reductions to unweighted (QP) Theorem: Given a -approximation FPRA for (QP), we can obtain a ( /( -1), )-approximation for (QP) for any >1. Theorem: Suppose we have an FPRA for (QP) that rounds x to an extreme point x such that Ax/ A x Ax (2-sided multiplicative guarantee) OR Ax- A x Ax+ (2-sided additive guarantee) Then, there exists a (1, O(1))-approximation for (QP).
Why is an FPRA useful? P x : optimal solution to Min cTx s.t. x P, Ax b y*: optimal dual values corresp. to side constraints Ax b x Then y* is an optimal solution to Lagrangian problem: Max { bTy + [min (c+ATy)Tx s.t. x P]: y 0} cy AND x* is optimal solution to inner problem: min (cy*)Tx s.t. x P
Why is an FPRA useful? P x : optimal solution to Min cTx s.t. x P, Ax b y*: optimal dual values corresp. to side constraints Ax b x Then y* is an optimal solution to Lagrangian problem: Max { bTy + [min (c+ATy)Tx s.t. x P]: y 0} x* is optimal solution to inner problem: min (cy*)Tx s.t. x P AND
Why is an FPRA useful? P x : optimal solution to Min cTx s.t. x P, Ax b y*: optimal dual values corresp. to side constraints Ax b x Then y* is an optimal solution to Lagrangian problem: Max { bTy + [min (c+ATy)Tx s.t. x P]: y 0} x* is optimal solution to inner problem: min (cy*)Tx s.t. x P all points on minimal face of P containing x* are optimal solutions to inner problem essentially unweighted problem output of FPRA has optimal cy*-cost ( = (cy*)Tx* ) AND
Summary and open questions Devise the first algorithm for chain-constrained spanning tree that gives O(1)-approx. to both cost and degrees Use Lagrangian relaxation in an unorthodox way to obtain a novel reduction to the unweighted setting Open questions What about the laminar case (i.e., C is laminar)? The reduction still works, so can focus on unweighted setting What about chain degree-constraints for other connectivity problems (e.g., Steiner forest etc.)? Other applications of our reduction? Iterative rounding/relaxation based algorithms? Not clear how to make this work even for chains.