Randomized Algorithms (Spring 2010)/Randomized approximation algorithms

From TCS Wiki
Revision as of 13:51, 26 May 2010 by imported>WikiSysop (→‎Randomized Rounding)
Jump to navigation Jump to search

Approximation Algorithms

Coping with the NP-hardness

Combinatorial approximation algorithms

LP-based approximation algorithms

Randomized Rounding

The integrality gap

Rounding LPs

Max-SAT

Covering and Packing