Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"
From esoterum.org
| Line 7: | Line 7: | ||
== HW 6 == | == HW 6 == | ||
1. [http://www.soe.ucsc.edu/classes/cmps132/Winter05/hw/hw8sols.pdf 2-SAT is in NP] | 1. [http://www.soe.ucsc.edu/classes/cmps132/Winter05/hw/hw8sols.pdf 2-SAT is in NP] | ||
| + | 2. A sub-optimal solution to TSP is a Hamiltonian Cycle. | ||
| + | |||
Revision as of 22:59, 11 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.
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
