CSE550 Combinatorial Algorithms/Intractability: Difference between revisions
From esoterum.org
Jump to navigationJump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
== Resources == | |||
*> [http://www.sce.carleton.ca/faculty/chinneck/po/Chapter2.pdf Linear Programming Introduction] | *> [http://www.sce.carleton.ca/faculty/chinneck/po/Chapter2.pdf Linear Programming Introduction] | ||
:-Unimodularity ensures that the solution to an LP will always be integer if all of the costs and constraints are also integer | :-Unimodularity ensures that the solution to an LP will always be integer if all of the costs and constraints are also integer | ||
| Line 12: | Line 13: | ||
:4. Finding disjoint paths with different path-costs: Complexity and algorithms | :4. Finding disjoint paths with different path-costs: Complexity and algorithms | ||
:*Randeep Bhatia · Murali Kodialam · T. V. Lakshman, [http://www.springerlink.com.ezproxy1.lib.asu.edu/content/x24w933w7vgu262x/fulltext.pdf "Finding disjoint paths with related path costs"], Springer Science+Business Media, LLC 2006 | :*Randeep Bhatia · Murali Kodialam · T. V. Lakshman, [http://www.springerlink.com.ezproxy1.lib.asu.edu/content/x24w933w7vgu262x/fulltext.pdf "Finding disjoint paths with related path costs"], Springer Science+Business Media, LLC 2006 | ||
== Midterm == | == Midterm == | ||
| Line 18: | Line 18: | ||
*Bin Zhang, Julie Ward, Qi Feng, [http://www.hpl.hp.com/techreports/2005/HPL-2005-121.pdf "Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing"], HP Laboratories Palo Alto, June 28, 2005 | *Bin Zhang, Julie Ward, Qi Feng, [http://www.hpl.hp.com/techreports/2005/HPL-2005-121.pdf "Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing"], HP Laboratories Palo Alto, June 28, 2005 | ||
*J. M. W. Rhys, [http://www.jstor.org.ezproxy1.lib.asu.edu/cgi-bin/jstor/printpage/00251909/di012665/01p0039r/0.pdf?backcontext=results&dowhat=Acrobat&config=&userID=81dbf4d5@asu.edu/01c0545010c0e9115c6b1c33c&0.pdf "A Selection Problem of Shared Fixed Costs and Network Flows"], Management Science, Vol. 17, No. 3, Theory Series (Nov., 1970), pp. 200-207 | *J. M. W. Rhys, [http://www.jstor.org.ezproxy1.lib.asu.edu/cgi-bin/jstor/printpage/00251909/di012665/01p0039r/0.pdf?backcontext=results&dowhat=Acrobat&config=&userID=81dbf4d5@asu.edu/01c0545010c0e9115c6b1c33c&0.pdf "A Selection Problem of Shared Fixed Costs and Network Flows"], Management Science, Vol. 17, No. 3, Theory Series (Nov., 1970), pp. 200-207 | ||
=== Q4 === | === Q4 === | ||
Revision as of 02:59, 18 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
- Linear Programming animation (simplex method)
- List of LP solvers (including NEOS)
- Integer Linear Programming Tutorial
- Interger Linear Programming Tutorial (CMU)
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
- Randeep Bhatia · Murali Kodialam · T. V. Lakshman, "Finding disjoint paths with related path costs", Springer Science+Business Media, LLC 2006
Midterm
Q1
- 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
