@Article{sandholm05a,
  author =	 {Tuomas Sandholm and Subhash Suri and Andrew Gilpin
                  and David Levine},
  title =	 {{CABOB}: a fast optimal algorithm for winner
                  determination in combinatorial auctions},
  journal =	 {Management Science},
  year =	 2005,
  volume =	 51,
  number =	 3,
  pages =	 {374--391},
  googleid = 	 {1_jUXZoZCYkJ:scholar.google.com/},
  abstract =	 {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. We also uncover interesting aspects of the
                  problem itself. First, problems with short bids,
                  which were hard for the first generation of
                  specialized algorithms, are easy. Second, almost all
                  of the CATS distributions are easy, and the run time
                  is virtually unaffected by the number of
                  goods. Third, we test several random restart
                  strategies, showing that they do not help on this
                  problem--the run-time distribution does not have a
                  heavy tail.},
  keywords =     {multiagent auctions combinatorial},
  url = 	 {http://jmvidal.cse.sc.edu/library/sandholm05a.pdf},
  cluster = 	 {9874451808776419543}
}