CABOB: a fast optimal algorithm for winner determination in combinatorial auctions. Combinatorial auctions where bidders can bid on bundles of items can lead to more economically efficient allocations, but determining the winners is NP-complete and inapproximable. We present CABOB, a sophisticated optimal search algorithm for the problem. It uses decomposition techniques, upper and lower bounding (also across components), elaborate and dynamically chosen bid-ordering heuristics, and a host of structural observations. CABOB attempts to capture structure in any instance without making assumptions about the instance distribution. Experiments against the fastest prior algorithm, CPLEX 8.0, show that CABOB is often faster, seldom drastically slower, and in many cases drastically faster-especially in cases with structure. CABOB’s search runs in linear space and has significantly better anytime performance than CPLEX.

References in zbMATH (referenced in 31 articles , 1 standard article )

Showing results 1 to 20 of 31.
Sorted by year (citations)

1 2 next

  1. Pan, Yunpeng; Liang, Zhe: Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems (2017)
  2. Karakaya, Gülşah; Köksalan, Murat: An interactive approach for bi-attribute multi-item auctions (2016)
  3. Lin, Geng; Zhu, Wenxing; Ali, M. Montaz: An effective discrete dynamic convexized method for solving the winner determination problem (2016)
  4. Landete, Mercedes; Monge, Juan Francisco; Rodríguez-Chía, Antonio M.: Alternative formulations for the set packing problem and their application to the winner determination problem (2013)
  5. Conitzer, Vincent; Sandholm, Tuomas: Computing optimal outcomes under an expressive representation of settings with externalities (2012)
  6. Gilpin, Andrew; Sandholm, Tuomas: Information-theoretic approaches to branching in search (2011)
  7. Boughaci, Dalila; Benhamou, Belaïd; Drias, Habiba: Local search methods for the optimal winner determination problem in combinatorial auctions (2010) ioport
  8. Ervasti, Valtteri; Leskelä, Riikka-Leena: Allocative efficiency in simulated multiple-unit combinatorial auctions with quantity support (2010)
  9. Harsha, Pavithra; Barnhart, Cynthia; Parkes, David C.; Zhang, Haoqi: Strong activity rules for iterative combinatorial auctions (2010)
  10. Stößer, Jochen; Neumann, Dirk; Weinhardt, Christof: Market-based pricing in grids: on strategic manipulation and computational cost (2010)
  11. Boughaci, Dalila; Benhamou, Belaïd; Drias, Habiba: A memetic algorithm for the optimal winner determination problem (2009) ioport
  12. Catalán, Jaime; Epstein, Rafael; Guajardo, Mario; Yung, Daniel; Martınez, Cristian: Solving multiple scenarios in a combinatorial auction (2009)
  13. Drexl, Andreas; Jørnsten, Kurt; Knof, Diether: Non-linear anonymous pricing combinatorial auctions (2009)
  14. Goossens, D. R.; Spieksma, F. C. R.: Exact algorithms for the matrix bid auction (2009)
  15. Özer, Ali Haydar; Özturan, Can: A model and heuristic algorithms for multi-unit nondiscriminatory combinatorial auction (2009)
  16. Alidaee, Bahram; Kochenberger, Gary; Lewis, Karen; Lewis, Mark; Wang, Haibo: A new approach for modeling and solving set packing problems (2008)
  17. Aparicio, Juan; Landete, Mercedes; Monge, Juan Francisco; Sirvent, Inmaculada: A new pricing scheme based on DEA for iterative multi-unit combinatorial auctions (2008)
  18. Mu’Alem, Ahuva; Nisan, Noam: Truthful approximation mechanisms for restricted combinatorial auctions (2008)
  19. Schnizler, Björn; Neumann, Dirk; Veit, Daniel; Weinhardt, Christof: Trading grid services - a multi-attribute combinatorial approach (2008)
  20. Stößer, Jochen; Neumann, Dirk: GreedEx---a scalable clearing mechanism for utility computing (2008)

1 2 next