Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"
From esoterum.org
| Line 70: | Line 70: | ||
:-Matching-based LP relaxation of edge-coloring gap should be an additive 1! There is a paper by Jeff Kahn, but it is somewhat difficult. | :-Matching-based LP relaxation of edge-coloring gap should be an additive 1! There is a paper by Jeff Kahn, but it is somewhat difficult. | ||
| + | === GLPsol and LP === | ||
*[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] | ||
| Line 77: | Line 78: | ||
*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) | *[http://center.uvt.nl/staff/haemers/reader05ico.pdf LP formulations] (covering, packing, partition) (non-linear information) | ||
| + | |||
| + | === Min-Cut Max-Floe === | ||
*Dan Bienstock, [http://www.jstor.org/view/0364765x/ap060062/06a00070/0 "Some Generalized Max-Flow Min-Cut Problems in the Plane"] Mathematics of Operations Research, Vol. 16, No. 2. (May, 1991), pp. 310-333. | *Dan Bienstock, [http://www.jstor.org/view/0364765x/ap060062/06a00070/0 "Some Generalized Max-Flow Min-Cut Problems in the Plane"] Mathematics of Operations Research, Vol. 16, No. 2. (May, 1991), pp. 310-333. | ||
*[http://legacy.orie.cornell.edu/~shmoys/or630/notes-06/lec03.pdf Linear Programming and set covering problems] (based on notes from Tardos) | *[http://legacy.orie.cornell.edu/~shmoys/or630/notes-06/lec03.pdf Linear Programming and set covering problems] (based on notes from Tardos) | ||
| + | |||
| + | === TSP === | ||
| + | *[http://www.unc.edu/~pataki/papers/teachtsp.pdf Teaching Integer Programming Using the TSP] | ||
Revision as of 23:34, 1 December 2007
Contents
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
- > The Algorithm Design Manual, Steven S. Skiena, Department of Computer Science State University of New York (Online)
- Good article on intractability from Princeton
- David S. Johnson, "The NP-Completeness Column: An Ongoing Guide", J. Algorithms 5, 147-160 (1984)
- > Alexander Schrijver, "On the history of combinatorial optimization (till 1960)"
- Network Programming (Internet Edition), Katta G. Murty
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
Final
Q2
Q3
Q4
- Handbook of Scheduling: Algorithms, Models, and Performance Analysis, By Joseph Y-T. Leung (bipartite multi-graph edge coloring)
Q5
- M. R. Garey; R. L. Graham; D. S. Johnson; D. E. Knuth, "Complexity Results for Bandwidth Minimization", SIAM Journal on Applied Mathematics, Vol. 34, No. 3., May, 1978
- David Muradian, "The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete", Theoretical Computer Science 307, 2003
Project
2. Linear program formulation and solving. You can examine one or more linear programming formulations for a speci�c problem. This should be done by using a free solver, such as GLPK and a modeling language such as AMPL or the subset of AMPL that comes with GLPK. (If you have access to CPLEX and/or real AMPL, that is also perfectly fine with me.) Your goal in this might be to examine and compare the solution times for several formulations of a problem (as in the mincut example), or to study the tightness of a relaxation (as in the case of Steiner trees and edge coloring). Some suggestions for this type of project:
- -Comparing minimum cut formulations (standard cut covering, polynomial-size directed flow formulation, compact formulation by Carr et al.).
- -Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).
- -Asymmetric TSP (Charikar, Goemans, Karloff).
- -Matching-based LP relaxation of edge-coloring gap should be an additive 1! There is a paper by Jeff Kahn, but it is somewhat difficult.
GLPsol and LP
- 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)
Min-Cut Max-Floe
- Dan Bienstock, "Some Generalized Max-Flow Min-Cut Problems in the Plane" Mathematics of Operations Research, Vol. 16, No. 2. (May, 1991), pp. 310-333.
- Linear Programming and set covering problems (based on notes from Tardos)
