Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints.
Niv BuchbinderJoseph NaorR. RaviMohit SinghPublished in: ICALP (1) (2012)
Keyphrases
- approximation algorithms
- facility location problem
- np hard
- constant factor approximation
- precedence constraints
- worst case
- special case
- vertex cover
- minimum cost
- online learning
- network design problem
- approximation ratio
- linear constraints
- approximation schemes
- primal dual
- greedy algorithm
- constant factor
- weighted sum
- randomized algorithms
- weighted graph
- undirected graph
- approximation guarantees
- metaheuristic