1y ago

17 Views

1 Downloads

637.48 KB

125 Pages

Transcription

The Primal-Dual Method for Approximation Algorithms Jochen Könemann University of Waterloo Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 1/44

What is the primal-dual method? What is the primal-dual method? Primal-Dual: First Steps Originally proposed by Dantzig, Ford, and Fulkerson in 1956 as an alternate method to solve linear programs exactly Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 2/44

What is the primal-dual method? What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Originally proposed by Dantzig, Ford, and Fulkerson in 1956 as an alternate method to solve linear programs exactly Method did not survive. but: Revised version of it has become immensely popular for solving combinatorial optimization problems. Group Strategyproof Mechanisms for Steiner Forests - p. 2/44

What is the primal-dual method? What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Originally proposed by Dantzig, Ford, and Fulkerson in 1956 as an alternate method to solve linear programs exactly Method did not survive. but: Revised version of it has become immensely popular for solving combinatorial optimization problems. Examples: Dijkstra’s shortest path algorithm, Ford and Fulkerson’s network flow algorithm, Edmond’s non-bipartite matching method, Kuhn’s assignment algorithm, . Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 2/44

What is the primal-dual method? What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Originally proposed by Dantzig, Ford, and Fulkerson in 1956 as an alternate method to solve linear programs exactly Method did not survive. but: Revised version of it has become immensely popular for solving combinatorial optimization problems. Examples: Dijkstra’s shortest path algorithm, Ford and Fulkerson’s network flow algorithm, Edmond’s non-bipartite matching method, Kuhn’s assignment algorithm, . Main feature: Reduce weighted optimization problems to easier unweighted ones. Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 2/44

What is the primal-dual method? What is the primal-dual method? Primal-Dual: First Steps All of the previous problems are in P. Can we extend this method to NP-hard problems? Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 3/44

What is the primal-dual method? What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 All of the previous problems are in P. Can we extend this method to NP-hard problems? Yes! Bar-Yehuda and Even use this in 1981 in their approximation algorithm for vertex-cover. Group Strategyproof Mechanisms for Steiner Forests - p. 3/44

What is the primal-dual method? What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 All of the previous problems are in P. Can we extend this method to NP-hard problems? Yes! Bar-Yehuda and Even use this in 1981 in their approximation algorithm for vertex-cover. Goemans and Williamson formalize this approach in 1992. Result is a general toolkit for developing approximation algorithms for NP-hard optimization problems. The last 10 years have seen literally hundreds of papers that use the primal-dual framework. Group Strategyproof Mechanisms for Steiner Forests - p. 3/44

What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: First Steps Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 4/44

An example: Vertex Cover What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Goal: Find a minimum subset of the vertices C such that e C 6 for all edges e. Group Strategyproof Mechanisms for Steiner Forests - p. 5/44

An example: Vertex Cover What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Goal: Find a minimum subset of the vertices C such that e C 6 for all edges e. Here’s a vertex cover of size 6. Group Strategyproof Mechanisms for Steiner Forests - p. 5/44

An ILP for Vertex Cover Variables: What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 6/44

An ILP for Vertex Cover Variables: For node i have variable xi . Want ( 1 : Node i in vertex cover xi 0 : Otherwise. What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Variables like this are called indicator variables. Group Strategyproof Mechanisms for Steiner Forests - p. 6/44

An ILP for Vertex Cover Variables: For node i have variable xi . Want ( 1 : Node i in vertex cover xi 0 : Otherwise. What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Variables like this are called indicator variables. Constraints: Each edge needs to be covered. Group Strategyproof Mechanisms for Steiner Forests - p. 6/44

An ILP for Vertex Cover Variables: For node i have variable xi . Want ( 1 : Node i in vertex cover xi 0 : Otherwise. What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Variables like this are called indicator variables. Constraints: Each edge needs to be covered. Example: Edge (0, 5) x0 x 5 1 Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 6/44

An ILP for Vertex Cover Variables: For node i have variable xi . Want ( 1 : Node i in vertex cover xi 0 : Otherwise. What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Variables like this are called indicator variables. Constraints: Each edge needs to be covered. Example: Edge (0, 5) x0 x 5 1 Objective function: Minimize cardinality of vertex cover. Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 6/44

An ILP for Vertex Cover Variables: For node i have variable xi . Want ( 1 : Node i in vertex cover xi 0 : Otherwise. What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Variables like this are called indicator variables. Constraints: Each edge needs to be covered. Example: Edge (0, 5) x0 x 5 1 Objective function: Minimize cardinality of vertex cover. minimize 9 X xj j 0 Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 6/44

Primal ILP What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms minimize X xv v V s.t. xv xu 1 (u, v) E xv {0, 1} v V Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 7/44

Dual LP What is the primal-dual method? Dual LP has a variable ye for each edge e E. Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm maximize X ye e E Petersen graph example Approximation algorithms s.t. Primal-Dual: Hitting Sets X ye 1 v V e δ(v) Primal-Dual: Steiner Trees ye 0 e E Primal Dual: MCF δ(v): Edges incident to vertex v V Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 8/44

Primal-dual technique: Main Ideas What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Construct integral primal and dual feasible solution at the same time: x and y Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 9/44

Primal-dual technique: Main Ideas What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Construct integral primal and dual feasible solution at the same time: x and y Show that X X xj α · yi j i For some α. Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 9/44

Primal-dual technique: Main Ideas What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms j Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Construct integral primal and dual feasible solution at the same time: x and y Show that X X xj α · yi i For some α. Prove a worst-case upper-bound on α. Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 9/44

Primal-dual technique: Main Ideas What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms j Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Construct integral primal and dual feasible solution at the same time: x and y Show that X X xj α · yi Primal Dual: MCF Jochen Könemann, September 25, 2004 i For some α. Prove a worst-case upper-bound on α. Result: For every instance we compute . 1. an integral and feasible primal solution x, and 2. a proof that its value is within a factor of α of the best possible solution Group Strategyproof Mechanisms for Steiner Forests - p. 9/44

Vertex-cover: A PD-Algorithm What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms 1: 2: 3: 4: 5: Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees z Primal Dual: MCF 6: 7: Jochen Könemann, September 25, 2004 yuv 0 for all edges (u, v) C while C is not a vertex cover do Choose uncovered edge (u, v) Increase yuv until X ywz 1 for z {u, v} C C {z} end while Group Strategyproof Mechanisms for Steiner Forests - p. 10/44

Petersen graph example What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal solution: Dual solution: Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 11/44

Petersen graph example What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal solution: Dual solution: Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 11/44

Petersen graph example What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal solution: Dual solution: Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 11/44

Petersen graph example What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal solution: Dual solution: Primal solution: 8 Dual solution: 5 Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 11/44

Petersen graph example What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Primal solution: Dual solution: Primal solution: 8 Dual solution: 5 Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Q: How bad can the primal/dual ratio be? Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 11/44

Petersen graph example What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Primal solution: Dual solution: Primal solution: 8 Dual solution: 5 Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Q: How bad can the primal/dual ratio be? A: Not too bad. The primal solution has at most two vertices per dual edge. Hence, we always have X ye C 2 · e Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 11/44

Approximation algorithms What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms The previous algorithm for vertex-cover is a 2-approximation algorithm. We also say: Its performance guarantee is 2. Formally: The algorithm return a solution that has size at most twice the optimum for all instances! Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 12/44

Approximation algorithms What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 The previous algorithm for vertex-cover is a 2-approximation algorithm. We also say: Its performance guarantee is 2. Formally: The algorithm return a solution that has size at most twice the optimum for all instances! Q: Given a problem and an LP with LP/IP-gap α 1. Can there be a primal-dual approximation algorithm using this LP with performance guarantee less than α? Group Strategyproof Mechanisms for Steiner Forests - p. 12/44

Approximation algorithms What is the primal-dual method? Primal-Dual: First Steps An example: Vertex Cover An ILP for Vertex Cover Dual LP PD: Main Ideas Vertex-cover: A PD-Algorithm Petersen graph example Approximation algorithms Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 The previous algorithm for vertex-cover is a 2-approximation algorithm. We also say: Its performance guarantee is 2. Formally: The algorithm return a solution that has size at most twice the optimum for all instances! Q: Given a problem and an LP with LP/IP-gap α 1. Can there be a primal-dual approximation algorithm using this LP with performance guarantee less than α? A: No! Cannot find a good dual lower-bound for IP/LP-gap instance. Group Strategyproof Mechanisms for Steiner Forests - p. 12/44

What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 13/44

How to hit sets. What is the primal-dual method? Primal-Dual: First Steps Let us define a general problem called Hitting Sets. Input: Ground set E and m subsets Primal-Dual: Hitting Sets Ti E How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees for 1 i m. Also have cost ce for all e E. Goal: Find H E of minimum total cost, s.t. Primal Dual: MCF H Ti 6 for all 1 i m. Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 14/44

How to hit sets. What is the primal-dual method? Primal-Dual: First Steps Let us define a general problem called Hitting Sets. Input: Ground set E and m subsets Primal-Dual: Hitting Sets Ti E How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees for 1 i m. Also have cost ce for all e E. Goal: Find H E of minimum total cost, s.t. Primal Dual: MCF H Ti 6 for all 1 i m. Q: How can we formulate vertex-cover as a hitting-set problem? Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 14/44

How to hit sets. What is the primal-dual method? Primal-Dual: First Steps Let us define a general problem called Hitting Sets. Input: Ground set E and m subsets Primal-Dual: Hitting Sets Ti E How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees for 1 i m. Also have cost ce for all e E. Goal: Find H E of minimum total cost, s.t. Primal Dual: MCF H Ti 6 for all 1 i m. Q: How can we formulate vertex-cover as a hitting-set problem? A: The ground-set E is the set of all vertices. Each edge (u, v) corresponds to a set {u, v} that needs to be hit. Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 14/44

How to hit sets. What is the primal-dual method? Primal-Dual: First Steps Let us define a general problem called Hitting Sets. Input: Ground set E and m subsets Primal-Dual: Hitting Sets Ti E How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees for 1 i m. Also have cost ce for all e E. Goal: Find H E of minimum total cost, s.t. Primal Dual: MCF H Ti 6 for all 1 i m. Q: Give a hitting-set formulation for shortest s, t-path in undirected graphs! Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 14/44

How to hit sets. What is the primal-dual method? Primal-Dual: First Steps Let us define a general problem called Hitting Sets. Input: Ground set E and m subsets Primal-Dual: Hitting Sets Ti E How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees for 1 i m. Also have cost ce for all e E. Goal: Find H E of minimum total cost, s.t. Primal Dual: MCF H Ti 6 for all 1 i m. Q: Give a hitting-set formulation for shortest s, t-path in undirected graphs! A: Ground set E is set of all edges. Sets to hit are all s, t-cuts. Convince yourself that the shortest s, t is the minimum-cost solution! Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 14/44

Hitting Set: Primal and Dual What is the primal-dual method? Primal-Dual: First Steps minimize Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover X ce · x e (P ) e E s.t. X xe 1 1 i m e Ti xe 0 e E Primal-Dual: Steiner Trees Primal Dual: MCF maximize m X yi (D) i 1 s.t. X yi ce e E Ti :e Ti yi 0 1 i m Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 15/44

Hitting Set: Primal-Dual algorithm What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Want to use the LP formulation and its dual to develop a primal-dual algorithm. Ideas, suggestions, . anybody? Analysis Set Cover Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 16/44

Hitting Set: Primal-Dual algorithm What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees Primal Dual: MCF Want to use the LP formulation and its dual to develop a primal-dual algorithm. Ideas, suggestions, . anybody? Recall from vertex-cover PD-algo: Keep feasible dual solution y and include vertex v into cover only if X yuv 1 (u,v) Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 16/44

Hitting Set: Primal-Dual algorithm What is the primal-dual method? Primal-Dual: First Steps Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Want to use the LP formulation and its dual to develop a primal-dual algorithm. Ideas, suggestions, . anybody? Recall from vertex-cover PD-algo: Keep feasible dual solution y and include vertex v into cover only if X yuv 1 Primal-Dual: Steiner Trees Primal Dual: MCF (u,v) Idea: Let H be the current hitting set, y be the corresponding dual, and let Ti be a set that has not been hit. Increase yi until X yj ce Tj :e Tj for some e Ti . Include e into H. Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 16/44

Analysis What is the primal-dual method? Primal-Dual: First Steps Let H be the final feasible hitting set and y the corresponding feasible dual solution. Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees X ce ? e H Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 17/44

Analysis What is the primal-dual method? Primal-Dual: First Steps Let H be the final feasible hitting set and y the corresponding feasible dual solution. Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm X Analysis Set Cover e H Primal-Dual: Steiner Trees ce X X yi e H Ti :e Ti Primal Dual: MCF Since ce Jochen Könemann, September 25, 2004 P Ti :e Ti yi ce when e is included into H. Group Strategyproof Mechanisms for Steiner Forests - p. 17/44

Analysis What is the primal-dual method? Primal-Dual: First Steps Let H be the final feasible hitting set and y the corresponding feasible dual solution. Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees Primal Dual: MCF X ce X X yi e H Ti :e Ti e H m X Ti H · yi i 1 Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 17/44

Analysis What is the primal-dual method? Primal-Dual: First Steps Let H be the final feasible hitting set and y the corresponding feasible dual solution. Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm X Analysis Set Cover ce Primal Dual: MCF yi e H Ti :e Ti e H Primal-Dual: Steiner Trees X X m X Ti H · yi i 1 Vertex cover: Ti ’s correspond to edges. Hence: Ti H 2! Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 17/44

Set Cover What is the primal-dual method? Primal-Dual: First Steps Problem input: Elements U and subsets S1 , . . . , Sn of U . Goal: Select smallest number of sets that cover U . Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Analysis Set Cover Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 18/44

Set Cover What is the primal-dual method? Primal-Dual: First Steps Problem input: Elements U and subsets S1 , . . . , Sn of U . Goal: Select smallest number of sets that cover U . Primal-Dual: Hitting Sets How to hit sets. Linear Program Primal-Dual Algorithm Theorem [Feige] Analysis Set Cover There is no (log(n) )-approximation for the set-cover problem and any 0 unless NP P. Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strate

Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 9/44 Primal-dual technique: Main Ideas Construct integral primal and dual feasible solution at the same time: x and y Show that X j xj X i yi For some . Prove a worst-case upper-bound .

Related Documents: