CSE550 Combinatorial Algorithms/Intractability

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

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 ?

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)