CO754 Approximation Algorithms Winter-2010
------------------------------------------

Tentative plan for lectures (4mar10, 6jan10)
---------------------------


[V.i]= Vazirani textbook, chapter i
[WS.i]= Williamson-Shmoys text, draft of Jan.2010, chapter i

week.1

[WS.1], [V.1]:		SCP (set covering problem), min vertex cover:
			IP, LP relaxation, algorithms for SCP:
			rounding, rounding dual soln., greedy method

[WS.1], [V.1,13,14,15]:	SCP, min vertex cover:
			greedy method and its analysis, primal-dual method

week.2

[WS.1], [V.13,14,15]:	 more on SCP, submodular SCP

[V.2]:			key problems with metric costs: TSP, steiner tree

week.3

[WS.7.4], [V.22]:	Network design:
			primal-dual method for Steiner forest

[WS.3.1], [V.8]:	Knapsack: dynamic programming, FPTAS

week.4

[WS.3.3], [V.9,10]:	bin packing:
			asymptotic PTAS
			(not done: PTAS for scheduling id machines)

[WS.10.1], [V.11]:	PTAS for Euclidean TSP

week.5

[V.29]:			hardness of approximation:
			gap preserving reductions,
			PCP theorem and implications,
			GNI (graph nonisomorphism) in PCP(poly(n),O(1))
			maxE3sat -> min vertex cover -> min steiner tree,
			max3Dmatching(B),
			PCP theorem -> max clique

week.6

[V.29]:			hardness of approximation:
			PCP theorem -> max clique
			g.p.reductions and "degree bounded" problems
			(not done: gap maxsat -> gap maxE3sat -> gap maxE3sat(B) )

			label cover, parallel repetition theorem
			hardness for SCP via B(M,L) set family

week.7

[WS.5], [V.14,16,19]:	randomized rounding:
			max cut, max sat, rounding LP for max sat [GW],
			rounding LP for SCP
			Chernoff bounds
			integer multicommodity flow (cong.min for EDP)
			(not done: multiway cut [CKR])

week.8

[WS.5]			randomized rounding:
			integer multicommodity flow (cong.min for EDP),
			uncapacitated facility location,
			derandomization

[WS.6], [V.26]:		SDP (semi-definite programming) for maxcut

week.9

[WS.6], [V.26]:         SDP (semi-definite programming) for maxcut,
				QP, graph-coloring

[WS.8], [V.18-21]:	metric methods & cut problems:
			multicut, balanced cut,
			min-cut linear arrangement

week.10

[WS.8], [V.18-21]:	metric methods & cut problems:
			multicut, balanced cut,
			probabilistic approximation of metrics

[WS.15], [V.21]:	sparsest cuts, metric embeddings

week.11

[WS.11], [V.23]:	iterative rounding method:
			degree-bounded network design

[V.28]:			approximate counting