Home | Publications | CS Home

The Compset Algorithm for Subset Selection


Yaniv Hamo and Shaul Markovitch. The Compset Algorithm for Subset Selection. In Proceedings of The Nineteenth International Joint Conference for Artificial Intelligence, 728-733 Edinburgh, Scotland, 2005.


Abstract

Subset selection problems are relevant in many domains. Unfortunately, their combinatorial nature prohibits solving them optimally in most cases. Local search algorithms have been applied to subset selection with varying degrees of success. This work presents Compset, a general algorithm for subset selection that invokes an existing local search algorithm from a random subset and its complementary set, exchanging information between the two runs to help identify wrong moves. Preliminary results on complex SAT, Max Clique, 0/1 Multidimensional Knapsack and Vertex Cover problems show that Compset improves the efficient stochastic hill climbing and tabu search algorithms by up to two orders of magnitudes.


Keywords: Subset Selection, Resource-Bounded Reasoning, Local Search
Secondary Keywords:
Online version:
Bibtex entry:
 @inproceedings{Hamo:2005:CAS,
  Author = {Yaniv Hamo and Shaul Markovitch},
  Title = {The Compset Algorithm for Subset Selection},
  Year = {2005},
  Booktitle = {Proceedings of The Nineteenth International Joint Conference for Artificial Intelligence},
  Pages = {728--733},
  Address = {Edinburgh, Scotland},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Hamo-Markovitch-ijcai2005.pdf},
  Keywords = {Subset Selection, Resource-Bounded Reasoning, Local Search},
  Secondary-keywords = {Anytime Algorithms},
  Abstract = {
    Subset selection problems are relevant in many domains.
    Unfortunately, their combinatorial nature prohibits solving them
    optimally in most cases. Local search algorithms have been applied
    to subset selection with varying degrees of success. This work
    presents Compset, a general algorithm for subset selection that
    invokes an existing local search algorithm from a random subset
    and its complementary set, exchanging information between the two
    runs to help identify wrong moves. Preliminary results on complex
    SAT, Max Clique, 0/1 Multidimensional Knapsack and Vertex Cover
    problems show that Compset improves the efficient stochastic hill
    climbing and tabu search algorithms by up to two orders of
    magnitudes.
  }

  }