The COMPSET Algorithm for Subset Selection

Hamo, Yaniv; Markovitch, Shaul

The COMPSET Algorithm for Subset Selection

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 728-732.

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.

Yaniv Hamo, and Shaul Markovitch. 2005. The COMPSET Algorithm for Subset Selection. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 728–732. https://ijcai.org/proceedings/2005/213

@inproceedings{ijcai2005p213,
  title     = {The COMPSET Algorithm for Subset Selection},
  author    = {Hamo, Yaniv and Markovitch, Shaul},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-05}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {728--732},
  year      = {2005},
  url       = {https://ijcai.org/proceedings/2005/213},
}

TY  - CPAPER
TI  - The COMPSET Algorithm for Subset Selection
AU  - Hamo, Yaniv
AU  - Markovitch, Shaul
T2  - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2005
SP  - 728
EP  - 732
UR  - https://ijcai.org/proceedings/2005/213
ER  -