Course CO2a: Combinatorial Optimization 2a
(LNMB, Fall 2011)

LNMB page: http://www.lnmb.nl/courses/CO2a.html
This page: http://www.win.tue.nl/~gwoegi/CO2a/
Lecturer: Gerhard Woeginger

• Exercises, first series (deadline Oct 12, 2011):   pdf
• Exercises, second series (deadline Oct 26, 2011):   pdf   (article1.pdf; article2.pdf)
• Exercises, third series (deadline Nov 9, 2011):   pdf
• Exercises, fourth series (deadline Nov 23, 2011):   pdf

• C.H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity, Dover, 1998.
  At www.amazon.com this book is $12.48 plus taxes plus shipping, and shipping is within 24 hours.
  At the book depository this book is EUR 13.29 including shipping, and shipping is within 48 hours.
  This pocket book is cheap, and highly recommended; it provides a lot of intuition and reads well.
  The course will cover material from Chapters 8.1-8.5; 15; 16; 17; 18; 19.
• J.K. Lenstra, A.H.G. Rinnooy Kan. Computational complexity of discrete optimization problems.
  Annals of Discrete Mathematics 4 (pp 121-140), 1979.
  You get a copy of this paper on Sep-12.
• E.H.L. Aarts, J.K. Lenstra. Introduction. Chapter 1 (pp 1-17).
  In: E.H.L. Aarts, J.K. Lenstra (eds). Local Search in Combinatorial Optimization. Wiley, Chichester, 1997.
  Find yourself a copy of this chapter. (The book is available at most university libraries.)
• (!!!New!!!) M.R. Fellows. Parameterized Complexity: The main ideas and connections to practical computing.
  In: R. Fleischer et al (eds). Experimental Algorithmics. Springer, LNCS 2547, 2002, pp 51-77.
  pdf-file

• 12-Sep-2011: (Introduction)
  problems; instances & size; algorithm & running time & polynomiality;
  P & NP; certificates; P versus NP; reductions; NP-completeness; SAT is NP-complete

• 19-Sep-2011: (NP-completeness)
  Some NP-complete problems: integer programming; clique; independent set; vertex cover;
  directed Hamiltonian cycle; undirected Hamiltonian cycle; TSP;

• 26-Sep-2011: (NP-completeness) More NP-complete problems: Exact cover; Subset sum; Partition;
  pseudo-polynomial time; strong NP-hardness; weak NP-hardness; Three-partition;
  co-NP; co-NP versus NP

• 3-Oct-2011: (Approximation algorithms)
  Vertex cover (greedy; matching; LP); Makespan (greedy); TSP (double-tree; tree+matching);
  preemptive scheduling with rejections (pp 11-15 in this pdf-file)

• 10-Oct-2011: (Approximation schemes)
  PTAS and FPTAS; three basic approaches for constructing schemes;
  Inapproximability: FPTAS (strong NP-hardness); PTAS (gap reductions; APX-hardness)
  (pp 8-50 in this pdf-file)

• 17-Oct-2011: (Local search)
  neighborhoods + PLS; 2-opt and k-opt for TSP; flip for Max-Cut; flip for Max-SAT; jump for Makespan;
  exact neighborhoods versus NP-hardness;
  quality of local optima (flip for Max-Cut; jump for Makespan; k-opt for TSP);
  time complexity of finding a local optimum (flip for Max-Cut; jump for Makespan); PLS-completeness

• 24-Oct-2011: (Parameterized algorithms)
  Parameterized problems; fpt-algorithms; FPT;
  kernelization; kernelization theorem;
  fpt-reductions; W[1], W[2], XP; W-hierarchy; W[1]-hardness.

• 31-Oct-2009: (Exact algorithms)
  Search tree algorithms (independent set; 3-Sat); dynamic programming (TSP; graph coloring);
  exploiting polynomial speedups (Subset Sum, MaxCut)
  (partially covered in pdf-file; see also: pdf-file)

• 7-Nov-2009: (Structured special cases)
  2-SAT; Independent set, clique, and chromatic number of interval graphs;
  Subset-Sum (super-increasing sequence); Knapsack (divisible item weights);
  TSP on Monge matrices

• A clean mathematical formulation of the "P versus NP" question by Stephen Cook.
• Stephen Cook's paper The Complexity of Theorem-Proving Procedures from 1971 contains the proof that SAT is NP-complete
• Richard Karp's landmark paper Reducibility Among Combinatorial Problems showed that 21 diverse combinatorial and graph theoretical problems are NP-complete.
• Richard Lipton: Is P=NP an Ill Posed Problem?
• Lance Fortnow: The Status of the P versus NP Problem (CACM, September 2009); highly recommended
• The New York Times, 7-Oct-2009, on "Solving the P-NP Puzzler"
  Quote: "[...] an esoteric branch of mathematics known as algebraic geometry [...]"
• The game that lead to Hamiltonian cycles
• Lots of information on the TSP.
• A nice instance of SUBSET-SUM (where items can be used multiple times). Can you help the waiter?
• Some lecture notes by Lex Schrijver on matchings
• Some lecture notes by David Williamson on Approximation Algorithms. That's old stuff from Fall'1998, but it still does read well.
• The book of Vijay Vazirani on Approximation Algorithms. Without doubt the best available book on this topic. Chapter 16 contains some nice LP-rounding results for Max-Satisfiability.
• Carla Gomes and Bart Selman: Hill Climbing Search
• WalkSAT: A famous local search algorithm for Satisfiability
• The book of Rod Downey and Mike Fellows on Parameterized Complexity. The first three chapters provide a very nice and gentle introduction into the field.
• Scott Aaronson's Complexity Zoo
• Scott Aaronson: NP-complete Problems and Physical Reality