Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
Niv BuchbinderJoseph NaorR. RaviMohit SinghPublished in: CoRR (2012)
Keyphrases
- approximation algorithms
- facility location problem
- np hard
- special case
- constant factor approximation
- precedence constraints
- vertex cover
- worst case
- minimum cost
- open shop
- set cover
- approximation ratio
- primal dual
- online learning
- approximation schemes
- online algorithms
- np hardness
- greedy algorithm
- randomized algorithms
- combinatorial auctions
- weighted sum
- planar graphs
- constraint programming