Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"

Revision as of 02:47, 26 November 2007

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

2. A sub-optimal solution to TSP is a Hamiltonian Cycle.

4. Finding disjoint paths with different path-costs: Complexity and algorithms

Randeep Bhatia · Murali Kodialam · T. V. Lakshman, "Finding disjoint paths with related path costs", Springer Science+Business Media, LLC 2006

1.

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

Bin Zhang, Julie Ward, Qi Feng, "Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing", HP Laboratories Palo Alto, June 28, 2005
J. M. W. Rhys, "A Selection Problem of Shared Fixed Costs and Network Flows", Management Science, Vol. 17, No. 3, Theory Series (Nov., 1970), pp. 200-207

@@ Line 21: / Line 21: @@
 :*[http://www.diku.dk/undervisning/2005v/404/tspappr.pdf Solution to part (a),(b)]
 :*[http://209.85.173.104/search?q=cache:qgZ0E6cTD20J:www.cs.uu.nl/docs/vakken/amc/lecture03-2.ps+%22asymmetric+metric+TSP%22&hl=en&ct=clnk&cd=1&gl=us Additional infor (a),(b), possible references for (c)]
+::-Theorem 1.2 (Kumar and Li, 2002) Any asymmetric TSP on n locations can be reducedto a symmetric TSP on 2n locations
 == Midterm ==