O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.
Amit AgarwalMoses CharikarKonstantin MakarychevYury MakarychevPublished in: STOC (2005)
Keyphrases
- approximation algorithms
- worst case
- vertex cover
- np hard
- lower bound
- randomized algorithms
- np hardness
- np complete
- special case
- exact algorithms
- optimization problems
- approximation schemes
- minimum cost
- primal dual
- branch and bound
- learning algorithm
- disjoint paths
- boolean formula
- greedy algorithms
- set cover
- practical problems
- uniform distribution
- greedy algorithm