@InProceedings{hoos00a,
  author =	 {Holger H. Hoos and Craig Boutilier},
  title =	 {Solving Combinatorial Auctions Using Stochastic
                  Local Search},
  googleid =	 {0GUZgHdTf-MJ:scholar.google.com/},
  booktitle =	 {Proceedings of the Seventeenth National Conference
                  on Artificial Intelligence and Twelfth Conference on
                  Innovative Applications of Artificial Intelligence},
  year =	 2000,
  pages =	 {22--29},
  publisher =	 {{AAAI} Press / The {MIT} Press},
  abstract =	 {Combinatorial auctions (CAs) have emerged as an
                  important model in economics and show promise as a
                  useful tool for tackling resource allocation in
                  AI. Unfortunately, winner determination for CAs is
                  NP-hard and recent algorithms have difficulty with
                  problems involving goods and bids beyond the
                  hundreds. We apply a new stochastic local search
                  algorithm, Casanova, to this problem, and
                  demonstrate that it finds high quality (even
                  optimal) solutions much faster than recently
                  proposed methods (up to several orders of
                  magnitude), particularly for large problems. We also
                  propose a logical language for naturally expressing
                  combinatorial bids in which a single logical bid
                  corresponds to a large (often exponential) number of
                  explicit bids. We show that Casanova performs much
                  better than systematic methods on such
                  problems. were placed, with the aim of maximizing
                  revenue. Because bundles generally overlap, this is
                  conceptually a straightforward optimization problem,
                  and is in fact equivalent to weighted set
                  packing. As a result, optimal winner determination
                  for CAs is NP-complete [16]. A number of complete
                  algorithms for winner determination have been
                  proposed, including dynamic programming models [16],
                  and algorithms for dealing with problems with
                  special structure. More recently, two proposals for
                  applying AI-style search techniques have been used
                  with some success for winner determination [7,
                  17]. In these proposals,},
  keywords =     {combinatorial auctions},
  url =		 {http://jmvidal.cse.sc.edu/library/hoos00a.pdf},
  cluster = 	 {16392912941367256528},
}