Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"

Revision as of 01:44, 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.

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 20: / Line 20: @@
 :*[http://www.cs.toronto.edu/~pmccabe/csc363-2005S/notes22.pdf Solution to part (a),(b)]
 :*[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)]
 == Midterm ==