CSE550 Combinatorial Algorithms/Intractability

• Linear Programming Introduction
• 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

Q4

• LP Primal Dual Tutorial ?