Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Prahladh HarshaMoses CharikarMatthew AndrewsSanjeev AroraSubhash KhotDana MoshkovitzLisa ZhangAshkan AazamiDev DesaiIgor GorodezkyGeetha JagannathanAlexander S. KulikovDarakhshan J. MirAlantha NewmanAleksandar NikolovDavid PritchardGwen SpencerPublished in: CoRR (2010)
Keyphrases
- approximation algorithms
- lecture notes
- computer science
- revised selected papers
- np hard
- revised papers
- special case
- vertex cover
- worst case
- minimum cost
- lecture notes in artificial intelligence
- summer school
- facility location problem
- international workshop
- network design problem
- exact algorithms
- machine learning
- international symposium
- approximation schemes
- open shop
- approximation ratio
- machine learning for multimodal interaction
- set cover
- primal dual
- np hardness
- constant factor
- randomized algorithms
- artificial intelligence
- precedence constraints
- advances in artificial intelligence
- invited paper
- approximation guarantees
- undirected graph
- polynomial time approximation
- game theory
- computational intelligence
- information retrieval
- data mining