Approximation Algorithms for Secondary Spectrum Auctions
Martin HoeferThomas KesselheimBerthold VöckingPublished in: CoRR (2010)
Keyphrases
- approximation algorithms
- combinatorial auctions
- np hard
- special case
- worst case
- minimum cost
- facility location problem
- vertex cover
- open shop
- winner determination
- randomized algorithms
- primal dual
- mechanism design
- exact algorithms
- set cover
- resource allocation
- approximation schemes
- network design problem
- constant factor
- approximation ratio
- auction mechanisms
- np hardness
- polynomial time approximation
- precedence constraints
- online auctions
- convergence rate
- linear program
- disjoint paths