16:711:513
Discrete Optimization
Wednesday 30:30  6:30 PM
Room 139, RUTCOR building, Busch Campus
Instructor
 Endre Boros,
 Office: 117 RUTCOR building, Busch Campus
 Phone: 7324453235
 Email: boros@rutcor.rutgers.edu
 URL: http://rutcor.rutgers.edu/~boros
Office Hours
 After class, or by
appointment.
Exams and Grading
 Final grades will be based on class activity, homeworks and the final.
Syllabus

 Review of linear programming, duality theorem, Farkas' lemma, ellipsoid algorithm; complexity theory; a sample combinatorial problem and its analysis.
 Introduction to integer programming, pseudoBoolean programming, overview of basic algorithms. Introduction to polyhedral combinatorics, analysis of spanning tree problems.
 Greedy algorithms, independence systems, matroids, submodular optimization.
 Short review of network optimization, and shortest path algorithms.
 Matching theory, theorems by Petersen, Berge, KönigEgerváry, Frobenius, and Hall. Algebraic and polyhedral descriptions, theorems by Tutte, Berge, Lovász, Gallai, Edmonds, Hoffman and Kruskal, Balinski, Nemhauser and Trotter; the Hungarian method, Edmonds' blossomshrinking algorithm, and Lovász's algorithm.
 Applications of matchings: chain covers and anti chains and Dilworth theorem; bistochastic matrices, theorem by Birkhoff and von Neumann; Euclidean TSP and Christofides' heuristic; maximum cuts in planar graphs.
 Stable matchings, GaleShapley theorem, polyhedral results.
 Knapsack problem, dynamic programming and approximation algorithms.
 Cuttingstock problems, GilmoreGomory algorithm, binpacking problems and approximations, theorems by de la Vega and Lueker, Garey, Graham, Johnson and Yao, and Karmarkar and Karp.
 Set covering problems, exact and approximation algorithms, theorems by Lovász and Stein, Chvátal, Johnson, and Papadimotriou and Steiglitz.
 General and binary integer programming, LP relaxation, rounding. Implicit enumeration and branchandbound tecniques.
 Unimodularity, total unimodularity, TDI systems; theorems of Hoffman and Kruskal, Veinott and Dantzig, GhouilaHouri, and Edmonds and Giles.
 Hilbert bases, integer version of Helly's and Caratheodory's theorems; results by Gordan, Doignon, Bell and Scarf, and Cook, Fonlupt and Schrijver.
 Value function, subadditive, surrogate and Lagrangean duality.
 Valid inequalities, cutting planes, Gomory's algorithm, Chvátal cuts, liftandproject algorithms by Lovász and Schrijver, and by Balas and Ceria.
Books about discrete optimization

 W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver:
Combinatorial Optimization
(Wiley, 1998)
 G. Cornuéjols: Combinatorial Optimization: Packing and Covering (SIAM, 2001)
 B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms (Springer, 2000)
 T. Lengauer:
Combinatorial Optimization in Circuit Layout Design (Wiley, 1990)
 G.L. Nemhauser and L.A. Wolsey:
Integer and Combinatorial Optimization
(Wiley, 1988)
 C.H. Papadimitriu and K. Steiglitz:
Combinatorial Optimization: Algorithms and Complexity (PrenticeHall, 1982)
 A. Schrijver: Combinatorial Optimization (vols. IIII) (Springer, 2002)
 A. Schrijver:
Theory of Linear and Integer Programming
(Wiley, 1986, reprinted 1999)
 L.A. Wolsey:
Integer Programming
(Wiley, 1998)