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.
This study proposes a hybrid framework that integrates a deep Q-network with a local search algorithm that outperforms baseline algorithms and exhibits strong generalization in the minimum weight k-path vertex cover problem.
This work introduces a novel exploration procedure, DFS-BGS, to tackle the problem of exploring an unknown n-node graph by k robots that must remain connected throughout the process, and analyzes its performance both theoretically and experimentally.
Dolev Mutzari, Y. Aumann, Sarit Kraus· Proceedings of the Thirty-Fi...· 0 citations
The optimal number of colors on two classes defined by block structure is determined and the first nontrivial color lower bounds for unrestricted recoloring are proved, which improves the previous five-color upper bound to a tight four.
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.
