Not Logged In

Combinatorial Auctions, Knapsack Problems, and Hill-Climbing Search

This paper examines the performance of hill­climbing algo­ rithms on standard test problems for combinatorial auctions (CAs). On single­unit CAs, deterministic hill­climbers are found to perform well, and their performance can be improved significantly by randomizing them and restarting them several times, or by using them collectively. For some problems this good performance is shown to be no better than chan­ cel; on others it is due to a well­chosen scoring function. The paper draws attention to the fact that multi­unit CAs have been studied widely un­ der a different name: multidimensional knapsack problems (MDKP). On standard test problems for MDKP, one of the deterministic hill­climbers generates solutions that are on average 99% of the best known solutions.

Citation

R. Holte. "Combinatorial Auctions, Knapsack Problems, and Hill-Climbing Search". Canadian Conference on Artificial Intelligence (CAI), Ottawa, Canada, pp 57-66, January 2001.

Keywords: combinatorial, knapsack, problems, machine learning
Category: In Conference

BibTeX

@incollection{Holte:CAI01,
  author = {Robert Holte},
  title = {Combinatorial Auctions, Knapsack Problems, and Hill-Climbing Search},
  Pages = {57-66},
  booktitle = {Canadian Conference on Artificial Intelligence (CAI)},
  year = 2001,
}

Last Updated: June 18, 2007
Submitted by Staurt H. Johnson

University of Alberta Logo AICML Logo