CSE550 Combinatorial Algorithms/Intractability: Difference between revisions
From esoterum.org
Jump to navigationJump to search
No edit summary |
No edit summary |
||
| Line 26: | Line 26: | ||
*[http://www-128.ibm.com/developerworks/linux/library/l-glpk1/ GNU Linear Programming Kit guide from IBM] | *[http://www-128.ibm.com/developerworks/linux/library/l-glpk1/ GNU Linear Programming Kit guide from IBM] | ||
*[http://www.engr.pitt.edu/hunsaker/1081/glpsol_tutorial.pdf GLPsol Tutorial] | *[http://www.engr.pitt.edu/hunsaker/1081/glpsol_tutorial.pdf GLPsol Tutorial] | ||
*[http://www.sce.carleton.ca/faculty/chinneck/po/Chapter7.pdf LP in Practice] | *[http://www.sce.carleton.ca/faculty/chinneck/po.html Practical Optimization: A Gentle Introduction] | ||
:-[http://www.sce.carleton.ca/faculty/chinneck/po/Chapter7.pdf Chapter 7. LP in Practice] | |||
:-> [http://www.sce.carleton.ca/faculty/chinneck/po/Chapter10.pdf Chapter 10. Network Flow Programming] | |||
Revision as of 02:57, 18 November 2007
- -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
