2019/03/01 by Sebastian Brandt, Klaus-Tycho Foerster, Brandt, Sebastian +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Game Theory and Applications #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1903.00581
openalex publication_date 2019/03/01 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
We study the problem of online graph exploration on undirected graphs, where\na searcher has to visit every vertex and return to the origin. Once a new\nvertex is visited, the searcher learns of all neighboring vertices and the\nconnecting edge weights. The goal such an exploration is to minimize its total\ncost, where each edge traversal incurs a cost of the corresponding edge weight.\nWe investigate the problem on tadpole graphs (also known as dragons, kites),\nwhich consist of a cycle with an attached path. Miyazaki et al. (The online\ngraph exploration problem on restricted graphs, IEICE Transactions 92-D (9),\n2009) showed that every online algorithm on these graphs must have a\ncompetitive ratio of 2-epsilon, but did not provide upper bounds for non-unit\nedge weights. We show via amortized analysis that a greedy approach yields a\nmatching competitive ratio of 2 on tadpole graphs, for arbitrary non-negative\nedge weights.\n