Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"
From esoterum.org
| Line 40: | Line 40: | ||
:-> [http://www.sce.carleton.ca/faculty/chinneck/po/Chapter10.pdf Chapter 10. Network Flow Programming] | :-> [http://www.sce.carleton.ca/faculty/chinneck/po/Chapter10.pdf Chapter 10. Network Flow Programming] | ||
*Robert Fourer, [http://www.att.net/s/editorial.dll?pnum=1&bfromind=7406&eeid=5535987&_sitecat=1522&dcatid=0&eetype=article&render=y&ac=0&ck=&ch=ne&rg=blsadstrgt&_lid=332&_lnm=tg+ne+topnews&ck= AMPL: "A Mathematical Programming Language"] | *Robert Fourer, [http://www.att.net/s/editorial.dll?pnum=1&bfromind=7406&eeid=5535987&_sitecat=1522&dcatid=0&eetype=article&render=y&ac=0&ck=&ch=ne&rg=blsadstrgt&_lid=332&_lnm=tg+ne+topnews&ck= AMPL: "A Mathematical Programming Language"] | ||
| + | *[http://center.uvt.nl/staff/haemers/reader05ico.pdf LP formulations] (covering, packing, partition) (non-linear information) | ||
Revision as of 16:10, 27 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)
- Opensource Algorithm Code, Zuse Institute
- Lectures from the University of Freiburg
- > List of NP-Hard problems
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
HW 7
- 1.
- Optimization Theory By Hubertus Th. Jongen, Klaus Meer, Eberhard Triesch, partial search result on Google book search
- Solution to part (a),(b)
- Solution to part (a),(b)
- 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
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
Q4
Project
- GNU Linear Programming Kit guide from IBM
- GLPsol Tutorial
- Practical Optimization: A Gentle Introduction
- Robert Fourer, AMPL: "A Mathematical Programming Language"
- LP formulations (covering, packing, partition) (non-linear information)
