Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"

Revision as of 23:12, 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 23: / Line 23: @@
 :*[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
+:*[http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=ArticleListURL&_method=list&_ArticleListID=654442605&_sort=d&view=c&_acct=C000059542&_version=1&_urlVersion=0&_userid=56861&md5=7c0e2798e0ed6ae5bd0b5865eea21691 Science Direct "Problems"]
 == Midterm ==
 === Q1 ===