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

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

• LP Primal Dual Tutorial ?

Project

• 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"