Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"
From esoterum.org
| Line 10: | Line 10: | ||
:3. [http://www.cit.gu.edu.au/teaching/3130CIT/lectures/complexity.pdf 3SAT reduction to NAESAT] | :3. [http://www.cit.gu.edu.au/teaching/3130CIT/lectures/complexity.pdf 3SAT reduction to NAESAT] | ||
: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 |
Revision as of 03:11, 13 November 2007
- Linear Programming Introduction
- 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
