Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders.
Shahar DobzinskiNoam NisanMichael SchapiraPublished in: Math. Oper. Res. (2010)
Keyphrases
- combinatorial auctions
- approximation algorithms
- np hard
- special case
- winner determination
- multi unit
- worst case
- mechanism design
- single item
- multi unit combinatorial auctions
- approximation ratio
- randomized algorithms
- vertex cover
- auction mechanisms
- constant factor
- multi item
- bidding strategies
- primal dual
- linear programming
- disjoint paths
- social welfare
- knapsack problem