Randomized Algorithms (Spring 2010)/Randomized approximation algorithms

From TCS Wiki
Revision as of 07:29, 27 May 2010 by imported>WikiSysop (→‎Scheduling)
Jump to navigation Jump to search

Approximation Algorithms

Coping with the NP-hardness

Combinatorial approximation algorithms

Scheduling

Scheduling is a class of problems. We consider a central problem in scheduling theory: the minimum makespan scheduling.

Knapsack

LP-based approximation algorithms

Randomized Rounding

The integrality gap

Randomized rounding

Max-SAT

Covering and Packing

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Randomized_Algorithms_(Spring_2010)/Randomized_approximation_algorithms&oldid=2701"