Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"

From esoterum.org
Jump to: navigation, search
Line 38: Line 38:
 
solver, such as GLPK and a modeling language such as AMPL or the subset of AMPL
 
solver, such as GLPK and a modeling language such as AMPL or the subset of AMPL
 
that comes with GLPK. (If you have access to CPLEX and/or real AMPL, that is
 
that comes with GLPK. (If you have access to CPLEX and/or real AMPL, that is
−
also perfectly �ne with me.) Your goal in this might be to examine and compare the
+
also perfectly fine with me.) Your goal in this might be to examine and compare the
 
solution times for several formulations of a problem (as in the mincut example), or to
 
solution times for several formulations of a problem (as in the mincut example), or to
 
study the tightness of a relaxation (as in the case of Steiner trees and edge coloring).
 
study the tightness of a relaxation (as in the case of Steiner trees and edge coloring).
 
Some suggestions for this type of project:
 
Some suggestions for this type of project:
−
ˆ Comparing minimum cut formulations (standard cut covering, polynomial-size directed flow formulation, compact formulation by Carr et al.).
+
:Comparing minimum cut formulations (standard cut covering, polynomial-size directed flow formulation, compact formulation by Carr et al.).
−
ˆ Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).
+
:Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).
−
ˆ Asymmetric TSP (Charikar, Goemans, Karloff).
+
:Asymmetric TSP (Charikar, Goemans, Karloff).
−
ˆ Matching-based LP relaxation of edge-coloring�gap should be an additive 1!
+
:Matching-based LP relaxation of edge-coloring gap should be an additive 1!
−
There is a paper by Jeff Kahn, but it is somewhat diffcult.
+
There is a paper by Jeff Kahn, but it is somewhat difficult.
  
 
*[http://www-128.ibm.com/developerworks/linux/library/l-glpk1/ GNU Linear Programming Kit guide from IBM]
 
*[http://www-128.ibm.com/developerworks/linux/library/l-glpk1/ GNU Linear Programming Kit guide from IBM]

Revision as of 16:18, 27 November 2007

Resources

-Unimodularity ensures that the solution to an LP will always be integer if all of the costs and constraints are also integer

HW 6

1. 2-SAT is in NP
2. A sub-optimal solution to TSP is a Hamiltonian Cycle.
3. 3SAT reduction to NAESAT
4. Finding disjoint paths with different path-costs: Complexity and algorithms

HW 7

1.
-Theorem 1.2 (Kumar and Li, 2002) Any asymmetric TSP on n locations can be reducedto a symmetric TSP on 2n locations

Midterm

Q1

Q4

Project

2. Linear program formulation and solving. You can examine one or more linear programming formulations for a speci�c problem. This should be done by using a free solver, such as GLPK and a modeling language such as AMPL or the subset of AMPL that comes with GLPK. (If you have access to CPLEX and/or real AMPL, that is also perfectly fine with me.) Your goal in this might be to examine and compare the solution times for several formulations of a problem (as in the mincut example), or to study the tightness of a relaxation (as in the case of Steiner trees and edge coloring). Some suggestions for this type of project:

Comparing minimum cut formulations (standard cut covering, polynomial-size directed flow formulation, compact formulation by Carr et al.).
Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).
Asymmetric TSP (Charikar, Goemans, Karloff).
Matching-based LP relaxation of edge-coloring gap should be an additive 1!

There is a paper by Jeff Kahn, but it is somewhat difficult.

-Chapter 7. LP in Practice
-> Chapter 10. Network Flow Programming
Retrieved from "https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&oldid=1263"