Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"

Revision as of 18:15, 30 November 2007

Resources

• > Linear Programming Introduction

-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)

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

• Science Direct "Problems"

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

• LP Primal Dual Tutorial ?

Final

Q2

• Minimum Cost Flow (Linear Programming)

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

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.

• GNU Linear Programming Kit guide from IBM
• GLPsol Tutorial
• Practical Optimization: A Gentle Introduction

-Chapter 7. LP in Practice

-> Chapter 10. Network Flow Programming

• Robert Fourer, AMPL: "A Mathematical Programming Language"
• LP formulations (covering, packing, partition) (non-linear information)
• 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)