Combinatorial Optimization
R. Inkulu at cse.iitg in Spring 2013


Intro to LP Intro to approximations Network flows Matchings Cuts Connectivity Shortest paths Tours Spanning trees and arborescences Planar graphs Coloring Matroids

* [WS]: The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, First Edition.
* [Vaz]: Approximation Algorithms by Vijay V. Vazirani, First Edition.
* [PS]: Combinatorial Optimization by Christos H. Papadimitriou and Kenneth Steiglitz, First Edition.
* [KV]: Combinatorial Optimization by Bernard Korte and Jens Vygen, Fifth Edition.
* [ScN]: A Course in Combinatorial Optimization by Alexander Schrijver, 2013.

* [KT]: Algorithm Design by Jon Kleinberg and Eva Tardos, First Edition.
* [MR]: Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan, First Edition.
* [D]: Graph Theory by Reinhard Diestel, Fifth Edition.
* [CLRS]: Introduction to Algorithms by Cormen, Leiserson, Riverst, and Stein, Third Edition.

* [TS] denotes slides are from a talk

* AR: additional reading (no lecture delivered)