@InProceedings{zurel01a,
  author =	 {Edo Zurel and Noam Nisan},
  title =	 {An Efficient Approximate Allocation Algorithm for
                  Combinatorial Auctions},
  googleid =	 {bRf21Waeh68J:scholar.google.com/},
  booktitle =	 {Proceedings of the {ACM} Conference on Electronic
                  Commerce},
  year =	 2001,
  abstract =	 {We propose a heuristic for allocation in
                  combinatorial auctions. We first run an
                  approximation algorithm on the linear programming
                  relaxation of the combinatorial auction. We then run
                  a sequence of greedy algorithms, starting with the
                  order on the bids determined by the approximate
                  linear program and continuing in a hill-climbing
                  fashion using local improvements in the order of
                  bids. We have implemented the algorithm and have
                  tested it on the complete corpus of instances
                  provided by Vohra and de Vries as well as on
                  instances drawn from the distributions of
                  Leyton-Brown, Pearson, and Shoham. Our algorithm
                  typically runs two to three orders of magnitude
                  faster than the reported running times of Vohra and
                  de Vries, while achieving an average approximation
                  error of less than 1\%. This algorithm can provide,
                  in less than a minute of CPU time, excellent
                  solutions for problems with over 1000 items and
                  10,000 bids. We thus believe that combinatorial
                  auctions for most purposes face no practical
                  computational hurdles.},
  keywords =     {combinatorial auctions},
  url =		 {http://jmvidal.cse.sc.edu/library/zurel01a.pdf},
  cluster = 	 {12648252243006855021},
}