Explore the world of Combinatorial Optimization through iterative methods, linear programming, and rounding techniques. Learn about Minimum Bounded Degree Spanning Tree (MBDST) problem and how iterative rounding and relaxation play a crucial role in solving complex optimization problems efficiently. Discover key results and theorems in the field.
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
Iterative Methods in Combinatorial Optimization Mohit Singh McGill University joint works with L.C. Lau, F. Grandoni, T. Kiraly, S. Naor, R. Ravi and M. Salavatipour
Combinatorial Optimization Easy Problems : polynomial time solvable (P) Spanning Trees Matchings Matroid Intersection Hard Problems : NP-hard Survivable Network Design Facility Location Scheduling Problems 2
Linear Programming Formulate Linear Program P NP-hard Show Integrality Round the fractional solution to obtain approximation algorithm Randomized Rounding Primal-Dual Schema Iterative Rounding 3
Typical Rounding: Optimal Fractional Solution Rounding Procedure LP Solver Integer Solution Problem Instance Iterative Rounding (Jain 98): -element ) 2-approximation Good Part Integer Optimal Fractional Solution Part LP Solver Problem Instance Residual Problem Too Fractional
Minimum Bounded Degree Spanning Tree Design a spanning tree Low cost Low degree at all nodes s.t. T is a spanning tree deg (v) B 8 v min c(T) Checking feasibility is NP-hard 3/18/2025 3/18/2025 5 5
Iterative Rounding and Relaxation Iterative Rounding works for easy problems. Iterative proofs of integrality of spanning tree, arborescene, matroid, matching, matroid intersection Iterative Relaxation Relax complicating constraints and bound violations. Extend these integrality results to approximation algorithms. 3/18/2025 7
Result Theorem [S., Lau 07]: There exists a polynomial time algorithm for MBDST problem which returns a tree of c(T) c(OPT) maximum degree B+1. OPT is the cheapest tree with maximum degree B. Resolved a conjecture of Goemans 91 and improved on Goemans 06. Generalizes a result of Furer and Raghavachari 92. 8
Outline Integrality of Spanning Tree B+1 result Extensions Conclusion and Open Problems 3/18/2025 9
Spanning Tree Polyhedron Integer program min e2 E ce xe s.t. e2 E(V) xe= |V|-1 Any tree has n-1 edges xe2 {0,1} 3/18/2025 10
Spanning Tree Polyhedron Integer program min e2 E ce xe s.t. e2 E(V) xe= |V|-1 e2 E(S) xe |S|-1 8 S V, |S| 2 xe2 {0,1} Any tree has n-1 edges Subtour elimination constraints E(S): set of edges with both endpoints in S. 3/18/2025 11
Spanning Tree Polyhedron Linear Integer program (Edmonds 71) min e2 E ce xe s.t. e2 E(V) xe= |V|-1 e2 E(S) xe |S|-1 8 S V, |S| 2 xe2 {0,1} 0 xe 1 Any tree has n-1 edges Subtour elimination constraints Equivalent compact formulations [Wong 80] Polynomial time separation [Cunningham 84] 3/18/2025 12
(Iterative) Rounding Spanning Trees Solve LP to obtain optimum extreme point x 1) 2) Remove all edges s.t. xe = 0 3) Return E (the non-zero edges) Claim: If |E|=|V|-1 then E is a MST. Proof: E feasible ) x(E)=|V|-1 )xe=18 e2 E ) E is a tree. 3/18/2025 13
Extreme Points and Uncrossing Claim: x is extreme ) |E| n-1 Fact: x extreme ) d linearly independent tight constraints. 3/18/2025 14
Extreme Points and Uncrossing Claim: x is extreme ) |E| n-1 Fact: x extreme ) d linearly independent tight constraints. e2 E(S)xe=|S|-1 Standard uncrossing )linearly independent set of constraints defining x can be chosen to form a laminar family. A[B B A A B 3/18/2025 3/18/2025 15
Extreme Points and Uncrossing Claim: x is extreme ) |E| n-1 Fact: x extreme ) d linearly independent tight constraints. e2 E(S)xe=|S|-1 Standard uncrossing )linearly independent set of constraints defining x can be chosen to form a laminar family. 3/18/2025 16
Extreme Points and Uncrossing Claim: x is extreme ) |E| n-1 Number of variables (dimension) = |E| Number of constraints = |L| ) |E|=|L| |L| is laminar )|L| n-1 ) |E| n-1 Theorem [Edmonds]: Spanning tree polyhedron is integral. 3/18/2025 17
Outline Integrality of Spanning Tree B+1 result Extensions Conclusion and Open Problems 3/18/2025 18
Bounded Degree Spanning Trees Extend spanning tree polyhedron Here W V. s.t. e2 E(V) xe= |V|-1 e2 E(S) xe |S|-1 8 S V e2 (v)xe Bv 8 v 2 W xe 0 min e2 E ce xe Spanning tree Degree bounds 3/18/2025 20
Obtaining B+1 Algorithm Solve LP to obtain extreme point x. 1. Remove all edges e s.t. xe=0. 2. Return E. 3. 3/18/2025 21
Obtaining B+1 Algorithm Relaxation Step While W Solve LP to obtain extreme point x. 1. Remove all edges e s.t. xe=0. 2. If 9 v2 W such that degE(v) Bv+1, then remove the degree constraint of v. Return E Lemma: Solution returned is a tree Optimal cost degE(v) Bv+1 3. 1. 2. 3. 22
Main Lemma Lemma: There exists v2 W such that degE(v) Bv+1 where E is the support of x. Proof: Tight constraints 1. Laminar Family: L 2 . Degree constraints: W = Variables: Edges E Will show |E|> |L|+|W| ) contradiction Collect 1 token for Each member of L Each vertex in W Extra token Redistribute 1 token for each edge. |E| total token. See [Bansal, Khandekar, Nagarajan 08] 3/18/2025 23
Charging Argument Simpler argument due to Bansal, Khandekar and Nagarajan 08. Redistribution: Degree constraint for u and v get (1-xuv)/2 tokens each. v u $1 (1-xuv)/2 (1-xuv)/2 3/18/2025 24
Charging Argument Simpler argument due to Bansal, Khandekar and Nagarajan 08. Redistribution: Degree constraint for u and v get (1-xuv)/2 tokens each. Smallest set containing u and v gets xuv tokens v u xuv $1 Collection: Tokens received : e2 (w) (1-xe)/2 (degE(w)-Bw)/2 1 (since degree constraint present) w 3/18/2025 25
Charging Argument Simpler argument due to Bansal, Khandekar and Nagarajan 08. Redistribution: Degree constraint for u and v get (1-xuv)/2 tokens each. Smallest set containing u and v gets xuv tokens v u xuv $1 Collection: S R2 x(E(S))=|S|-1 R1 - x(E(Ri))=|Ri|-1 Tokens to S= Integer 3/18/2025 26
General Methodology Constrained Problem Base Problem Side Constraints 3/18/2025 27
More General Structures Matroid Submodular Flow Degree Constraints Degree Constraints Thm[Kiraly, Lau, S 08]: Additive approximation for degree constrained matroid basis and degree constrained submodular flow problem. See BKNP 10 for more general structures. 3/18/2025 33
Multi-Criteria Spanning Tree Spanning Tree lengthi (T) Li Thm [Grandoni, Ravi, S. 09]: Iterative Relaxation gives (1+ )-approximation for fixed 3/18/2025 34
General Methodology Base Problem Structured side constraints in structured problems are easy to handle Side Constraints 3/18/2025 35
Applications* Topolgy Control for Future Airborne Networks, Krishnamurthi et al 2009. Deploying Mesh Nodes under non-uniform propogation, Robinson et al, 2009 3/18/2025 36
Conclusion Iterative Rounding and Relaxation Obtain new iterative proofs of classical integrality results Extend these integrality results to multi-criteria optimization and obtain additive approximations Open Problems OPT+1 for Bin Packing? OPT + log2 n. Karp Karmarkar 82. Discrepancy of Sets? Beck, Fiala 81, Bansal 10. 3/18/2025 37
Conclusion Introduced iterative relaxation Obtain new iterative proofs of classical integrality results Extend these integrality results to multi-criteria optimization and obtain additive approximations Also extends iterative rounding methods. 3/18/2025 39
