跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 nn-vertex graphs, the best known competitive ratio has been O(log⁡n)O(\log n), achieved by several algorithms, among them the hierarchical depth-first search of Megow, Mehlhorn, and Schweitzer. We give an algorithm with competitive ratio (2+o(1))ln⁡n/ln⁡ln⁡n{(2+o(1))}\ln n/\ln\ln n for known~nn. 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 bb of the weight class can grow with~nn. The leading constant 22 is tight for our choice of base. Without knowing nn, restarts with increasing size guesses give upper bounds with leading constant 44 for a fixed schedule and 22 in expectation for a randomly shifted schedule. If the weights lie in a known range [1,2k][1,2^k] with k≥4k\ge4, choosing b=k/log⁡2kb=k/\log_2 k gives a competitive ratio of O(k/log⁡k)O(k/\log k) without knowing nn.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 nn-vertex graphs, the best known competitive ratio has been O(log⁡n)O(\log n), achieved by several algorithms, among them the hierarchical depth-first search of Megow, Mehlhorn, and Schweitzer. We give an algorithm with competitive ratio (2+o(1))ln⁡n/ln⁡ln⁡n{(2+o(1))}\ln n/\ln\ln n for known~nn. 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 bb of the weight class can grow with~nn. The leading constant 22 is tight for our choice of base. Without knowing nn, restarts with increasing size guesses give upper bounds with leading constant 44 for a fixed schedule and 22 in expectation for a randomly shifted schedule. If the weights lie in a known range [1,2k][1,2^k] with k≥4k\ge4, choosing b=k/log⁡2kb=k/\log_2 k gives a competitive ratio of O(k/log⁡k)O(k/\log k) without knowing nn.

查看此版本解读 →查看此版本原文 ↗