Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems.
Nikhil R. DevanurKamal JainBalasubramanian SivanChristopher A. WilkensPublished in: CoRR (2019)
Keyphrases
- approximation algorithms
- online algorithms
- resource allocation problems
- worst case
- resource allocation
- np hard
- lower bound
- average case
- online learning
- upper bound
- learning algorithm
- resource constraints
- competitive ratio
- special case
- vertex cover
- approximation ratio
- greedy algorithm
- precedence constraints
- constant factor
- computational complexity
- vc dimension
- theoretical analysis
- search space
- support vector