← 研踪 PaperTrailarXiv:2611.14755 · v1
A Sublogarithmic Competitive Algorithm for Online Graph Exploration
首次提交 2026-11-11 05:31
版本更新 2026-11-11 05:31
雷达观测 2026-11-13 10:09
摘要
In online graph exploration, an agent must visit every vertex of an unknown weighted graph and return to its start, learning the incident edges at each vertex it visits. On -vertex graphs, the best known competitive ratio has been , achieved by several algorithms, among them the hierarchical depth-first search of Megow, Mehlhorn, and Schweitzer. We give an algorithm with competitive ratio for known~. Like hierarchical depth-first search, it groups the edges into geometric weight classes and searches depth-first between components of lighter edges. Unlike it, the agent tours each component along a minimum spanning tree for the original weights, so only crossings between components pay for rounding, and the base of the weight class can grow with~. The leading constant is tight for our choice of base. Without knowing , restarts with increasing size guesses give upper bounds with leading constant for a fixed schedule and in expectation for a randomly shifted schedule. If the weights lie in a known range with , choosing gives a competitive ratio of without knowing .
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-11 05:31 · 最新观测版本
A Sublogarithmic Competitive Algorithm for Online Graph Exploration
In online graph exploration, an agent must visit every vertex of an unknown weighted graph and return to its start, learning the incident edges at each vertex it visits. On -vertex graphs, the best known competitive ratio has been , achieved by several algorithms, among them the hierarchical depth-first search of Megow, Mehlhorn, and Schweitzer. We give an algorithm with competitive ratio for known~. Like hierarchical depth-first search, it groups the edges into geometric weight classes and searches depth-first between components of lighter edges. Unlike it, the agent tours each component along a minimum spanning tree for the original weights, so only crossings between components pay for rounding, and the base of the weight class can grow with~. The leading constant is tight for our choice of base. Without knowing , restarts with increasing size guesses give upper bounds with leading constant for a fixed schedule and in expectation for a randomly shifted schedule. If the weights lie in a known range with , choosing gives a competitive ratio of without knowing .
查看此版本解读 →查看此版本原文 ↗