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
• > 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
• > A Compendium of NP-Complete 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 ?

Final

Q2

• Minimum Cost Flow (Linear Programming)
• Caterer Problem (Network graph)
• S. Vajda, "An Outline of Linear Programming", Journal of the Royal Statistical Society, 1955

Q3

• Max-Cut, Min-Flow and information on complementary slackness
• Duality and Complementary Slackness
• Max Flow - Min Cut via Linear Programming Duality

Q4

• Handbook of Scheduling: Algorithms, Models, and Performance Analysis, By Joseph Y-T. Leung (bipartite multi-graph edge coloring)
• Taehan Lee, Sungsoo Park, "An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links", European Journal of Operational Research, November 2001
• William Cook, László Lovász, Paul D. Seymour, "Combinatorial Optimization: Papers from the Dimacs Special Year", Mathematics, 1995
• Richard Cole, Kirstin Ost, Stefan Schirra, "Edge­Coloring Bipartite Multigraphs in 0(E log D) Time", April 18, 2000

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

Moses Charikar, Michel X. Goemans, Howard Karloff, "On the Integrality Ratio for Asymmetric TSP", Annual IEEE Symposium on Foundations of Computer Science, 2004

-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

-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)
• AMPL FAQ

Min-Cut Max-Flow

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

TSP

• Teaching Integer Programming Using the TSP
• A.J. Orman, H.P. Williams, "A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem", July 2005