@InProceedings{fujishima99a,
  author =	 {Yuzo Fujishima and Kevin Leyton-Brown and Yoav
                  Shoham},
  title =	 {Taming the Computational Complexity of Combinatorial
                  Auctions: Optimal and Approximate Approaches},
  googleid =	 {5ef8b4HHSAEJ:scholar.google.com/},
  booktitle =	 {Proceedings of the Sixteenth International Joint
                  Conference on Artificial Intelligence},
  year =	 1999,
  pages =	 {548--553},
  publisher =	 {Morgan Kaufmann Publishers Inc.},
  abstract =	 {In combinatorial auctions, multiple goods are sold
                  simultaneously and bidders may bid for arbitrary
                  combinations of goods. Determining the outcome of
                  such an auction is an optimization problem that is
                  NP-complete in the general case. We propose two
                  methods of overcoming this apparent
                  intractability. The first method, which is
                  guaranteed to be optimal, reduces running time by
                  structuring the search space so that a modified
                  depth-first search usually avoids even considering
                  allocations that contain conflicting bids. Caching
                  and pruning are also used to speed searching. Our
                  second method is a heuristic, market-based
                  approach. It sets up a virtual multi-round auction
                  in which a virtual agent represents each original
                  bid bundle and places bids, according to a fixed
                  strategy, for each good in that bundle. We show
                  through experiments on synthetic data that (a) our
                  first method finds optimal allocations quickly and
                  offers good anytime performance, and (b) in many
                  cases our second method, despite lacking guarantees
                  regarding optimality or running time, quickly
                  reaches solutions that are nearly optimal.},
  keywords =     {combinatorial auctions},
  url =		 {http://jmvidal.cse.sc.edu/library/fujishima99a.pdf},
  cluster = 	 {92543151104649189}
}