It is proved that the competitive ratio of the online graph exploration problem is at least 4, improving on the previously best known lower bound of 10/3.
Abstract
In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to its starting position. We prove that the competitive ratio of this problem is at least 4, improving on the previously best known lower bound of 10/3. A key ingredient of our proof is showing that several restrictions can be imposed on the agent's behavior without affecting the competitive ratio. As a byproduct, we also obtain that certain graph properties, such as the triangle inequality or being subcubic, can be assumed without affecting the competitive ratio.
The minimum weight k-path vertex cover problem is defined on a vertex-weighted graph G, where the objective is to find a vertex subset S such that every path of order k contains at least one vertex in S, while minimizing the total weight of S. For any integer k ≥ 2, this problem is NP-hard on general graphs. In this st...
Multi-robot graph exploration is a central problem in robotics, planning, and multi-agent systems. In this work, we consider the problem of exploring an unknown n-node graph by k robots that must remain connected throughout the process. Such a connectivity is frequently required for safety reasons, and naturally arises...
Dolev Mutzari, Y. Aumann, Sarit Kraus· Proceedings of the Thirty-Fi...· 0 citations
We study exploration of anonymous, port-free graphs by a single agent with no internal memory. To compensate for the lack of memory, the agent uses writable vertex colors as external memory. From every starting vertex, the agent must visit all vertices, return to its start, and terminate there. Throughout, recoloring i...
Shoma Hiraoka, Shun Imori, Shota Takahashi et al.· 0 citations
We present an average case model of classical problems in combinatorial optimization where there are color constraints. In all cases we seek some (spanning) sub-structure of a complete graph of minimum cost. The edges are randomly colored either red or blue. We bias against the red edges by placing a bound on the numbe...
Patrick Bennett, A. Frieze, Wesley Pegden· 0 citations
This paper presents an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model and gives a 1.5-competitive algorithm and provide a matching lower bound.
Júlia Baligács, B. Bosek, Y. Disser et al.· Embedded Systems and Applica...· 1 citation
We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from $1/4$ to $2/5$, improving on the long-standing bound of Chekuri, Mydlarz, and Shepherd~\cite{CMS}. We give the proof in two stages. First, a surprisingly simple packing lemma and an inductive coloring...
Elfarouk Harb· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
