# The Primal-Dual Method For Approximation Algorithms - Yale University

1y ago
17 Views
637.48 KB
125 Pages
Last View : 9d ago
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-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-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:

May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)

Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .

Relations between Primal and Dual If the primal problem is Maximize ctx subject to Ax b, x ‚ 0 then the dual is Minimize bty subject to Aty ‚ c (and y unrestricted) Easy fact: If x is feasible for the primal, and y is feasible for the dual, then ctx bty So (primal optimal) (dual optimal) (Weak Duali

On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.

̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions

Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have

BEEF Primal Cut Weight Range Guide PRIMAL CARCASE - PRIMAL CUT WEIGHT RANGES CUT * H.A.M. NO. 160-180kg 180-220kg 220-260kg 260-300kg This information is to be used as a GUIDE ONLY. * H.A.M. - Handbook of Australian Meat Reference Cut Item and Code Number. GUIDE TO CARCASE BODY YIELD PRIMAL CUTS ACCOUNT FOR : 60% TRIMMINGS :

ASTM INTERNATIONAL Helping our world work better Standards Catalog 2016 www.astm.org Highlights in this issue: 24 ook of B Standards 2 uilding Codes B 9 nline TrainingO 6 MNL 43 - 3rd 13 Proficiency Testing Standards Books Journals and Software Training Laboratory QA Programs. What’s New from ASTM International ASTM Compass Your Portal for Standards, Testing, Learning & More Give your .