Searching a Fixed graph

摘要

We study three combinatorial optimization problems related to searching a graph that is known in advance, for an item that resides at an unknown node. The search ratio of a graph is the optimum competitive ratio. We also define the randomized search ratio. Finally, the traveling repairman problem seeks to minimize the expected time of visit to the unknown node, given some distribution on the nodes. All three of these novel graph-theoretic parameters are NP-complete-and MAXSNP-hard-to compute exctly; we prresent interesting approximation algorithms for each. We also show that the randomized search ratio and the traveling repariman problem are related via duality and polyhedaral separation.