Approximation Algorithms for Combinatorial Optimization Book

	Approximations of independent sets in graphs	1
	Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems	15
	The steiner tree problem and its generalizations	33
	Approximation schemes for covering and scheduling on related machines	39
	One for the price of two: A unified approach for approximating covering problems	49
	Approximation of geometric dispersion problems	63
	Approximating k-outconnected subgraph problems	77
	Lower bounds for on-line scheduling with precedence constraints on identical machines	89
	Instant recognition of half integrality and 2-approximations	99
	The t-vertex cover problem: Extending the half integrality framework with budget constraints	111
	A new fully polynomial approximation scheme for the knapsack problem	123
	On the hardness of approximating spanners	135
	Approximating circular arc colouring and bandwidth allocation in all-optical ring networks	147
	Approximating maximum independent set in k-clique-free graphs	159
	Approximating an interval scheduling problem	169
	Finding dense subgraphs with semidefinite programming	181
	Best possible approximation algorithm for MAX SAT with cardinality constraint	193
	Author Index	201