Online exploration of weighted graphs
One agent must visit every node of an unknown weighted graph and return to its start node, learning the edges at each node only when it gets there; how close to a shortest tour can its cost be?
Problem statement and measuresexpand
A single agent starts at a node \(s\) of an unknown connected undirected graph \(G=(V,E)\) with \(n\) nodes; every edge \(e\) has a non-negative weight \(\mathrm{wt}(e)\). Nodes and edges carry distinct identifiers. When the agent visits a node for the first time it learns the identifiers of its neighbours and the identifiers and weights of the edges to them. Crossing an edge has a cost equal to its weight. The agent must visit every node and return to the start node \(s\); its walk is then a tour. An algorithm is measured by its competitive ratio: the supremum, over all graphs and start nodes, of the cost of its tour divided by \(\mathrm{OPT}\), the cost of a shortest closed walk that visits every node (an optimal travelling-salesperson tour of \(G\)); for a randomized algorithm the expected cost is used. Unless a setting says otherwise the algorithm is deterministic, the graph is arbitrary and nothing about it is known in advance. Memory and computation are unbounded: the question is what the lack of information costs. Since \(\mathrm{OPT}\) lies between the weight of a minimum spanning tree and twice that weight, a depth-first search that ignores the weights already explores trees optimally, and the difficulty lies in the cycles.
Measures: Competitive ratio, worst-case cost of the agent's tour divided by OPT, the cost of a shortest tour.
Complete graphs, uniform weight estimates
verifiedOn complete graphs whose weights all lie in \([1, \vartheta]\) with \(\vartheta < 2\), recomputing the best walk after each step is \(\tfrac{1+\vartheta}{2}\)-competitive, which is optimal.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Node identifiers: labelled nodes
- Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
- Randomness: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- Knowledge of the graph: weight estimates
- The agent is given \(G\) and, for every edge \(e\), an interval \([\mathrm{wt}^-(e), \mathrm{wt}^+(e)]\) that contains \(\mathrm{wt}(e)\), with \(\mathrm{wt}^+(e) \le \vartheta\,\mathrm{wt}^-(e)\) for a factor \(\vartheta \ge 1\) (their \(\alpha\)); the exact weight of \(e\) is revealed when the agent visits an end of \(e\) Gehnen et al. 2025.
- Excluded minors: any graph
- \(G\) is any connected graph.
- Topology: complete graph
- \(G=K_n\): every pair of nodes is adjacent.
What is known
- complete graph on \(2j\) nodes, every weight announced in \([1, \vartheta]\), \(\vartheta \le 2\)
- edges at the first \(j\) nodes visited have weight 1, edges revealed later weight \(\vartheta\) (Theorem 10); for \(\vartheta > 2\) the same construction gives \(3/2\) (Remark 11), and an analogous one works on \(K_{j,j}\)
Results, in order of publication
Introductory and current best (Theorem 6, Corollary 8): after every step, recompute a walk through the unvisited nodes that is shortest when unrevealed weights take their upper ends. On such graphs it takes the cheapest edge to an unvisited node (Lemma 7). The same holds on every graph in which each path extends to a Hamiltonian path to the end node, including \(K_{j,j}\) and \(K_{j+1,j}\) (Corollary 9).
Open questions
None recorded for this variant.
Notes
On grids with uniform estimates and \(\vartheta < 2\) the recomputing algorithm is no better than \(\vartheta\)-competitive (Theorem 12 of Gehnen et al. 2025). Checked against the full text (arXiv v1, 2025).
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.