论文标题
改进了竞争图探索的下限
Improved Lower Bound for Competitive Graph Exploration
论文作者
论文摘要
我们在竞争比率上提供了10/3的改进，以探索一个无方向性的边缘加权图，并带有单个代理，该图需要在访问所有顶点后需要返回起始位置。我们假设代理商对访问的顶点的所有边缘有充分的了解，尤其是顶点具有唯一的标识符。 Dobrev等人的界限改善了2.5的下限。 [Sirocco'12]并为平面图提供，它补充了Kalyanasundaram和Pruhs [TCS'94]的16上限。一般而言，是否可以达到恒定的竞争比率仍然开放的问题。
We give an improved lower bound of 10/3 on the competitive ratio for the exploration of an undirected, edge-weighted graph with a single agent that needs to return to the starting location after visiting all vertices. We assume that the agent has full knowledge of all edges incident to visited vertices, and, in particular, vertices have unique identifiers. Our bound improves a lower bound of 2.5 by Dobrev et al. [SIROCCO'12] and also holds for planar graphs, where it complements an upper bound of 16 by Kalyanasundaram and Pruhs[TCS'94]. The question whether a constant competitive ratio can be achieved in general remains open.
