An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem.
Christos KalaitzisPublished in: SODA (2016)
Keyphrases
- approximation guarantees
- integrality gap
- approximation algorithms
- greedy algorithm
- approximation ratio
- linear programming relaxation
- lower bound
- multi class
- np hard
- linear program
- search algorithm
- objective function
- machine learning
- minimum cost
- bayesian networks
- learning algorithm
- kernel classifiers
- genetic algorithm