Search in a Small World

Walsh, Toby

Search in a Small World

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Search. Pages 1172-1176.

Abstract

In a graph with a "small world" topology, nodes are highly clustered yet the path length between them is small. Such a topology can make search problems very difficult since local decisions quickly propagate globally. We show that graphs a<>sociated with many different search problems have a small world topology, and that the cost of solving such search problems can have a heavy-tailed distribution. The strategy of randomization and restarts appears to eliminate these heavy tails. A novel restart schedule in which the cutoff bound is increased geometrically appears particularly effective.

Toby Walsh. 1999. Search in a Small World. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99. IJCAI, 1172–1176. https://ijcai.org/proceedings/1999/166

@inproceedings{ijcai1999p166,
  title     = {Search in a Small World},
  author    = {Walsh, Toby},
  booktitle = {Proceedings of the Sixteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-99}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Thomas Dean},
  pages     = {1172--1176},
  year      = {1999},
  note      = {Search},
  url       = {https://ijcai.org/proceedings/1999/166},
}

TY  - CPAPER
TI  - Search in a Small World
AU  - Walsh, Toby
T2  - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1999
SP  - 1172
EP  - 1176
UR  - https://ijcai.org/proceedings/1999/166
ER  -