Sampling Combinatorial Spaces Using Biased Random Walks

Erenrich, Jordan; Selman, Bart

Sampling Combinatorial Spaces Using Biased Random Walks

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1376-1379.

Abstract

For probabilistic reasoning, one often needs to sample from a combinatorial space. For example, one may need to sample uniformly from the space of all satisfying assignments. Can state-of-the-art search procedures for SAT be used to sample effectively from the space of all solutions? And, if so, how uniformly do they sample? Our initial results find that on the positive side, one can find all solutions to a given instance. Nevertheless, sampling can be highly biased. This research provides a starting point for the development of more balanced procedures.

Jordan Erenrich, and Bart Selman. 2003. Sampling Combinatorial Spaces Using Biased Random Walks. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 1376–1379. https://ijcai.org/proceedings/2003/204

@inproceedings{ijcai2003p204,
  title     = {Sampling Combinatorial Spaces Using Biased Random Walks},
  author    = {Erenrich, Jordan and Selman, Bart},
  booktitle = {Proceedings of the Eighteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-03}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Georg Gottlob},
  pages     = {1376--1379},
  year      = {2003},
  url       = {https://ijcai.org/proceedings/2003/204},
}

TY  - CPAPER
TI  - Sampling Combinatorial Spaces Using Biased Random Walks
AU  - Erenrich, Jordan
AU  - Selman, Bart
T2  - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2003
SP  - 1376
EP  - 1379
UR  - https://ijcai.org/proceedings/2003/204
ER  -