Graph Exploration with Edge Weight Estimates

\'Emile Naquin; Matthias Gehnen; Ralf Klasing

REVIEW 3 major objections 2 minor 30 references

Graph Exploration with Edge Weight Estimates

T0 review · 3 major / 2 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that the uncertainty factor α is the exact competitive ratio for general graph exploration with edge-weight estimates, and (1+α)/2 on complete graphs.

desk verdict The GEEWE model is a nice idea and the α upper bound is clean, but both lower-bound proofs have serious holes and the complete-graph lower bound contradicts the model's own revelation rule. read the letter →

arxiv 2501.18496 v1 pith:OOS2SJAL submitted 2025-01-30 cs.DS

Matthias Gehnen , Ralf Klasing , Émile Naquin This is my paper · ORCID

classification cs.DS MSC 68W2705C8568Q25

keywords graphexplorationtravellingsalesmanedgeweightestimatesonlinealgorithmscompetitiveratioadaptiveuncertainty

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces a middle ground between offline TSP and online graph exploration: the graph structure is known in advance, but each edge's true cost is revealed only when one of its endpoints is visited, and before that only an interval $[\ell(e), u(e)]$ is known. The central question is how much this uncertainty costs, measured by the competitive ratio as a function of $\alpha$, the largest ratio $u(e)/\ell(e)$ over all edges. For general graphs and $\alpha \le 2$, the paper claims no algorithm can achieve a competitive ratio better than $\alpha$, and a trivial algorithm that precomputes the cheapest walk from the lower bounds attains it. On complete graphs and complete balanced bipartite graphs with uniform announced weights $[1,\alpha]$, an adaptive algorithm that recalculates the worst-case shortest walk after each revealed edge achieves $(1+\alpha)/2$, with a matching lower bound. The paper closes with a conjecture that $(1+\alpha)/2$ is achievable for every graph with uniform announced weights and $\alpha \le 2$.

What carries the argument

The key machinery is the recursive component construction behind the general lower bound. A depth-$i$ component is built from $k$ depth-$(i-1)$ components connected in a row by level-$i$ edges announced in $[k^i, \alpha k^i]$; the adversary reveals the level-$i$ edges incident to a component's start vertex as cheap ($k^i$) and those incident to its end vertex as expensive ($\alpha k^i$). The proof's recurrence charges the online algorithm an extra $(\alpha-1)k^i$ per component, assuming it enters each component through the start vertex, while an offline walk enters through the end and leaves through a cheap start edge. The second central object is the adaptive exploration algorithm; under the hypotheses of Theorem 6 it degenerates to repeatedly taking the cheapest edge toward an unvisited vertex (the nearest-neighbour rule, Lemma 7), and that local behaviour is what drives the $(1+\alpha)/2$ ratio.

What would settle it

Take the recursive instance of Theorem 3 with $\alpha<2$ and have the algorithm move first along the cheap edge from the top-level start to the end vertex of the first component, then traverse every component from end to start and leave each through its cheap start-incident edges. If this strategy completes with cost $i(k+1)k^i + k^{i+1}$ on a depth-$i$ instance, the claimed $\alpha$ lower bound for general graphs does not follow from the given construction.

Watch

Extended reading notes

Core claim

The paper establishes that the gap between the announced upper and lower edge bounds, quantified by $\alpha$, sets the achievable competitive ratio for graph exploration. Theorem 3 asserts that for $\alpha \le 2$, every online algorithm on general graphs must pay at least $\alpha$ times the offline optimum on some instance, and Theorem 5 shows the bound is tight: precomputing the optimal walk using only the lower bounds and following it, without ever reacting to revealed weights, is $\alpha$-competitive. For complete graphs with uniform announcements $[1,\alpha]$, the adaptive exploration algorithm, which at each step recalculates the cheapest walk from the current vertex to the end that visits all unvisited vertices, is claimed to be $(1+\alpha)/2$-competitive (Theorem 6), and Theorem 10 proves this is best possible on complete graphs. The paper therefore positions the estimates model as a semi-online problem whose optimal competitive ratios interpolate between 1 and $\alpha$ depending on the graph class.

Load-bearing premise

Everything rests on the 'without loss of generality' claim that any exploration algorithm reaches the start vertex of each recursive component before its end vertex; if an algorithm can enter through the end terminal and leave through the cheap start edge, the per-component extra charge of $(\alpha-1)k^i$ need not be paid.

Editorial extensions

If this is right

On general graphs with $\alpha \le 2$, no adaptive strategy beats the precomputed lower-bound walk; the announced interval factor is the exact worst-case price of not knowing edge costs in advance.
On complete and complete balanced bipartite graphs with uniform intervals $[1,\alpha]$, the adaptive exploration algorithm is exactly $(1+\alpha)/2$-competitive, so the midpoint between the lower and upper bound is the best possible guarantee.
For $\alpha > 2$, the lower bounds saturate at $2$ (general graphs) and $3/2$ (complete graphs), so the model's interesting regime is $\alpha \le 2$.
On cycles, known graph-exploration lower bounds transfer when $\alpha$ is large enough; on tadpole graphs the identifiable path prevents the two-vertex dead-end constructions from carrying over.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The 'without loss of generality' in Theorem 3 may be removable: on the recursive construction the top-level entry edges to the first component are revealed cheap, so a valid strategy could enter each component through its end terminal and leave through the cheap start edges, matching the offline walk's cost. If that strategy succeeds, the general-graph lower bound would shrink, while the $(1+\alph
The conjecture that $(1+\alpha)/2$ holds for all graphs with uniform announcements could first be tested on grids, since Theorem 12 shows the adaptive algorithm itself fails there; a different algorithm would need to exploit the grid's structure without the Hamiltonian-path trap.
The model suggests a natural refinement where interval endpoints may depend on traversal direction; the ratio-symmetric constructions in this paper indicate that such directional estimates would alter the competitive ratio, possibly to the midpoint of the direction-specific factors.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

This paper introduces a sensible semi-online model — graph exploration with edge weight estimates — where the graph is known but each edge weight lies in an interval [1, α] and is revealed when an incident vertex is visited. That model sits naturally between offline TSP and fully online graph exploration, and the simple precomputing-on-lower-bounds algorithm (Theorem 5) gives a clean α competitive ratio. The adaptive exploration algorithm and the (1+α)/2 upper bound for complete graphs and complete bipartite graphs are also worth taking seriously; I did not find an obvious hole in the proof of Theorem 6.

The problem is the lower bounds. Theorem 10 claims no algorithm can beat (1+α)/2 on complete graphs, but the adversary violates Definition 2. If all edges incident to the vertices in A are revealed as 1 during the first phase, then every A–B edge is already fixed at 1 before B is ever visited. The adversary cannot later declare those edges to be α. An online algorithm can alternate between a new B vertex and an old A vertex, pay only 1 per edge, and achieve cost at most 2k−1, not (1+α)k. This is not a minor technicality; it destroys a headline optimality claim.

The general-graph lower bound, Theorem 3, also has a problematic 'without loss of generality' step. The construction lets the algorithm enter the first subcomponent through either endpoint cheaply, so declaring that the start is always reached before the end is not obviously harmless. The construction is symmetric enough that this might be repairable, but as written the proof has a real gap.

So the paper's main optimality claims are not established. The model and the upper bounds remain interesting starting points, and the conjecture about uniform weights on all graphs is a reasonable open problem. But the current version cannot be accepted, because the matching lower bounds are the reason to care about the upper bounds, and one of them is internally inconsistent with the model.

If I were an editor, I would not desk-reject this — a good referee can catch these issues and the model is worth further work — but this is a clear reject-and-revise situation. The authors need to redesign the Theorem 10 adversary (or weaken the claim) and fix the WLOG in Theorem 3.

Referee Report

3 major / 2 minor

Summary. The manuscript introduces the Graph Exploration with Edge Weight Estimates (GEEWE) problem, in which the graph structure and an interval [ℓ(e), u(e)] for each edge are known in advance, but the actual weight w(e) is revealed only when the agent visits an incident vertex. The paper claims three main results: (1) for general graphs and α ≤ 2, no algorithm can beat competitive ratio α, and a simple precomputed lower-bound walk matches this bound; (2) an adaptive re-optimization algorithm achieves competitive ratio (1+α)/2 on complete graphs and complete bipartite graphs with uniform announcements [1, α]; and (3) this ratio is best possible, even on complete graphs, via a matching lower bound. The upper-bound arguments are simple and plausible, but the matching lower bound on complete graphs is internally inconsistent with the model, and the general lower-bound proof contains an unjustified 'without loss of generality' step. The paper therefore does not establish its headline optimality claims.

Significance. The model is attractive: it occupies a natural middle ground between offline TSP and online graph exploration, and the idea of an adaptive algorithm that re-optimizes after each weight revelation is worth studying. If the claimed bounds were correct, the paper would give a clean interpolation: a tight α bound for general graphs and a tight (1+α)/2 bound for complete graphs with uniform announcements. The paper also has some genuine strengths: the simple lower-bound-walk algorithm of Theorem 5 is a parameter-free construction, the proofs are self-contained, and there is no fitted constant or circular reasoning. However, the complete-graph lower bound is the centerpiece of the paper's positive story, and it fails under Definition 2. The general-graph lower bound also has a proof gap. As a result, the main optimality claims are not currently supported.

major comments (3)

[Section 2, Theorem 3] The adversarial construction is inconsistent with Definition 2. Once the first k vertices (set A) have been visited, every edge incident to any A vertex has already been revealed, including every edge between A and the future set B. Therefore the statement 'every newly revealed edge has a weight α (the edges going to vertices in A are still of weight 1)' can apply only to edges inside B, not to A-B edges. A concrete algorithm can start at a1, follow the walk a1, b1, a2, b2, ..., ak, bk, ak, and end at ak, visiting all 2k vertices using only A-B edges of weight 1. This walk has cost 2k, whereas the proof claims the algorithm is forced to pay (1+α)k. Since an optimal offline walk costs at least 2k−1, the algorithm's competitive ratio on this instance is at most 2k/(2k−1), which contradicts the claimed lower bound (1+α)/2 for α<2. Thus Theorem 10 is false as stated, and the matching lower bound for complete graphs collapses.
[Section 2, Theorem 3] The proof relies on the assertion that 'without loss of generality the algorithm reaches the start vertex of each component before reaching the end vertex' (paragraph after Figure 1). This is load-bearing because the recurrence charges an extra (α−1)k^i for each component on the assumption that the algorithm is forced to leave through an end-incident expensive edge. However, the construction uses the start/end labels to decide which incident edges are revealed as k^i and which as αk^i, so the two terminals are not interchangeable after the algorithm has moved: renaming the terminals changes the adversarial edge weights. The proof must either fix a single assignment of weights that forces the claimed cost for every algorithm or give a separate argument showing that entering through the 'end' side cannot improve the total. This gap may be repairable, but it is not repaired in the text.
[Section 3.1, Lemma 7] Lemma 7 is central to Theorem 6 and its corollaries, but its proof is informal. It asserts that a Hamiltonian option 'beats every option that involves visiting vertices twice' without analyzing the case where revisiting a vertex uses a cheap, already-revealed edge. A rigorous proof must show that any walk with a repeated vertex can be shortcut to a simple Hamiltonian walk without increasing the worst-case cost; such a shortcut argument requires a direct edge between the relevant endpoints (true for complete graphs, but not for the general hypothesis of Theorem 6, which only assumes that every path extends to a Hamiltonian path). Since the competitive-ratio proof of Theorem 6 assumes the algorithm's walk has no repeated vertices, this gap should be closed or the theorem should be restricted to complete graphs with an explicit metric-shortcut argument.

minor comments (2)

[Section 3.2, Theorem 12] The grid construction is hard to verify from the figure and the prose. The text should specify n explicitly, describe the exact alternative walk (which edges are traversed twice), and show the calculation leading to the cost 6√n α + (√n − 2)√n so that the claimed convergence to α can be checked.
[Throughout] There are numerous typos and grammatical slips (for example 'trave rses' in the abstract and 'then the maximum factor' in Theorem 3). A careful proofreading pass is needed before resubmission.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's bounds are proved from explicit adversary constructions and self-contained arguments, and the sole self-citation is related-work context rather than load-bearing evidence.

full rationale

I walked the derivation chain. Theorem 3 constructs a recursive instance with explicit edge announcements and reveals and derives the lower bound by induction; no fitted parameter or predicted quantity is reused as an input. Theorem 5 proves the precomputed lower-bound walk is alpha-competitive directly from the definitions of the announced interval and alpha, without assuming the conclusion. Theorems 6, 10, and 12 are likewise self-contained: Theorem 6 is proved from a lemma about the adaptive algorithm's greedy behavior, Theorem 10 gives an explicit K_{2k} instance and compares the algorithm's cost with an explicit optimal path, and Theorem 12 gives an explicit grid construction. The only self-citation is [18] (Gehnen et al.) in the related-work discussion of online algorithms with estimates; it motivates the modeling framework but is not used to justify any theorem or to rule out alternative algorithms. No parameter is fitted to data and then renamed a prediction, and no result is imported from the authors' prior work as a uniqueness or impossibility theorem. A skeptical concern about Theorem 10's consistency with Definition 2 (edges incident to visited vertices are revealed with weight 1, so A-B edges may already be fixed as cheap when B is reached) is a possible correctness gap in the adversary construction, not a circularity: the paper does not define its conclusion into its assumptions. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities. The axioms listed are either explicit domain assumptions or hidden premises in the lower-bound proofs that contradict the model definition. The two ad hoc axioms are the load-bearing flaws.

assumptions (3)

ad hoc to paper The lower-bound constructions may assume the algorithm cannot infer which terminal of a recursive component is the cheap-exit end until it arrives and may be forced to reach the designated start before the end.
Used in Theorem 3 to justify charging an extra (α−1)k^i per component; the construction does not enforce it because both entry edges to the first component are revealed cheap, allowing the algorithm to enter at the end and leave at the start.
ad hoc to paper Edges incident to a visited vertex are not considered revealed for lower-bound purposes until the second endpoint is visited.
Theorem 10's adversary changes edges from A to B to α after B is first visited, which Definition 2 forbids because those edges were already revealed when the A endpoint was visited.
domain assumption Each path can be extended to a Hamiltonian path from start to distinct end vertex (Hamiltonian-extension property).
This is the explicit premise of Theorem 6 and is satisfied by complete graphs and complete balanced bipartite graphs; it is not an unstated assumption but a domain assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Graph Exploration with Edge Weight Estimates." pith.science (2026). https://pith.science/paper/OOS2SJAL

@misc{pith2026250118496,
  author       = {Pith},
  title        = {Pith review of: Graph Exploration with Edge Weight Estimates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OOS2SJAL}},
  note         = {Machine review of arXiv:2501.18496}
}

abstract

In the Travelling Salesman Problem, every vertex of an edge-weighted graph has to be visited by an agent who traverses the edges of the graph. In this problem, it is usually assumed that the costs of each edge are given in advance, making it computationally hard but possible to calculate an optimal tour for the agent. Also in the Graph Exploration Problem, every vertex of a given graph must be visited, but here the graph is not known in the beginning - at every point, an algorithm only knows about the already visited vertices and their neighbors. Both however are not necessarily realistic settings: Usually the structure of the graph (for example underlying road network) is known in advance, but the details are not. One usually has a prediction of how long it takes to traverse through a particular road, but due to road conditions or imprecise maps the agent might realize that a road will take slightly longer than expected when arriving on it. To deal with those deviations, it is natural to assume that the agent is able to adapt to the situation: When realizing that taking a particular road is more expensive than expected, recalculating the tour and taking another road instead is possible. We analyze the competitive ratio of this problem based on the perturbation factor $\alpha$ of the edge weights. For general graphs we show that for realistic factors smaller than $2$ there is no strategy that achieves a competitive ratio better than $\alpha$, which can be matched by a simple algorithm. In addition, we prove an algorithm which has a competitive ratio of $\frac{1+\alpha}{2}$ for restricted graph classes like complete graphs with uniform announced edge weights. Here, we present a matching lower bound as well, proving that the strategy for those graph classes is best possible. We conclude with a remark about special graph classes like cycles.

Figures

Figures reproduced from arXiv: 2501.18496 by the authors.

**Figure 1.** An example instance with the announcements of recursion depth 2 with k = 3 and α = 2. An online algorithm needs to traverse from s2 to t2. The edges of level 0 are just given with the weight 1, as they will be presented with weight 1 anyway. Depending on the decisions of the algorithm, the other edges will either have a value of the upper or lower bound. and traversing each of the k components costs at least (i − 1)… view at source ↗

**Figure 2.** Every edge is announced with [1, α] and revealed with the labeled weight. The adaptive exploration algorithm will traverse on the broad edges, and will not take the small ones (so every second layer). An alternative solution would take the continuous ones (and takes some edges twice in the bottom layer), and ignore the dashed ones. The adaptive exploration algorithm therefore walks on a Hamiltonian path, where each … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 29 canonical work pages

[1]

In: Structural Information an d Communication Com- plexity - 31st International Colloquium, SIROCCO 2024

van den Akker, E., Buchin, K., Foerster, K.: Multi-agent o nline graph exploration on cycles and tadpole graphs. In: Structural Information an d Communication Com- plexity - 31st International Colloquium, SIROCCO 2024. Spr inger (2024)

work page 2024
[2]

Algorithmica 29(4), 560–581 (2001)

Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.: Algorithms for the on-line travelling salesman. Algorithmica 29(4), 560–581 (2001)

work page 2001
[3]

In: Proceedings of the 53rd Annual ACM SIGACT Symposiu m on Theory of Computing

Azar, Y., Leonardi, S., Touitou, N.: Flow time scheduling with uncertain processing time. In: Proceedings of the 53rd Annual ACM SIGACT Symposiu m on Theory of Computing. STOC 2021, Association for Computing Machine ry (2021)

work page 2021
[4]

In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Azar, Y., Leonardi, S., Touitou, N.: Distortion-oblivio us algorithms for minimiz- ing ﬂow time. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM (2022)

work page 2022
[5]

In: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Azar, Y., Peretz, E., Touitou, N.: Distortion-Oblivious Algorithms for Schedul- ing on Multiple Machines. In: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Schloss Dagstuhl – Leibniz-Zent rum für Informatik (2022)

work page 2022
[6]

In: 31st Annual European Symposium on Algo rithms, ESA 2023

Baligács, J., Disser, Y., Heinrich, I., Schweitzer, P.: E xploration of graphs with excluded minors. In: 31st Annual European Symposium on Algo rithms, ESA 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023) 15

work page 2023
[7]

In: 31st Annual European Symposium o n Algorithms (ESA 2023)

Bampis, E., Escoﬃer, B., Gouleakis, T., Hahn, N., Lakis, K ., Shahkarami, G., Xefteris, M.: Learning-Augmented Online TSP on Rings, Tree s, Flowers and (Al- most) Everywhere Else. In: 31st Annual European Symposium o n Algorithms (ESA 2023). vol. 274 (2023)

work page 2023
[8]

Opera- tions Research 16(3), 538–558 (1968)

Bellmore, M., Nemhauser, G.L.: The traveling salesman pr oblem: A survey. Opera- tions Research 16(3), 538–558 (1968). https://doi.org/10.1287/opre.16.3.538

work page doi:10.1287/opre.16.3.538 1968

Show all 30 references

[9]

Theoretical Computer Scie nce 868 (2021)

Birx, A., Disser, Y., Hopp, A.V., Karousatou, C.: An impro ved lower bound for competitive graph exploration. Theoretical Computer Scie nce 868 (2021)

2021
[10]

In- formation and Computation 289(Part A) (2022)

Böckenhauer, H., Fuchs, J., Unger, W.: Exploring sparse graphs with advice. In- formation and Computation 289(Part A) (2022)

2022
[11]

: The online knapsack problem: Advice and randomization

Böckenhauer, H., Komm, D., Královič, R., Rossmanith, P. : The online knapsack problem: Advice and randomization. Theoretical Computer S cience 527 (2014)

2014
[12]

Cam- bridge University Press (1998)

Borodin, A., El-Yaniv, R.: Online computation and compe titive analysis. Cam- bridge University Press (1998)

1998
[13]

: Online graph exploration on a restricted graph class: Optimal solutions for tadpole g raphs

Brandt, S., Foerster, K.T., Maurer, J., Wattenhofer, R. : Online graph exploration on a restricted graph class: Optimal solutions for tadpole g raphs. Theoretical Com- puter Science 839 (2020)

2020
[14]

Carnegie Mellon University 3, 10 (03 2022)

Christoﬁdes, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Carnegie Mellon University 3, 10 (03 2022)

2022
[15]

Dantzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solutio n of a large-scale traveling- salesman problem. Oper. Res. 2(4), 393–410 (1954)

1954
[16]

In: Structural Information and Communication Complexity - 19t h International Col- loquium, SIROCCO 2012

Dobrev, S., Královic, R., Markou, E.: Online graph explo ration with advice. In: Structural Information and Communication Complexity - 19t h International Col- loquium, SIROCCO 2012. Springer (2012)

2012
[17]

Proceedings of the AAA I Conference on Artiﬁcial Intelligence 36(9) (2022)

Eberle, F., Lindermayr, A., Megow, N., Nölke, L., Schlöt er, J.: Robustiﬁcation of Online Graph Exploration Methods. Proceedings of the AAA I Conference on Artiﬁcial Intelligence 36(9) (2022)

2022
[18]

In: 41st International Symposium on Theoreti cal Aspects of Computer Science (STACS 2024)

Gehnen, M., Lotze, H., Rossmanith, P.: Online Simple Kna psack with Bounded Predictions. In: 41st International Symposium on Theoreti cal Aspects of Computer Science (STACS 2024). vol. 289. Schloss Dagstuhl – Leibniz- Zentrum für Informatik (2024)

2024
[19]

Theoretical Computer Science 130(1) (1994)

Kalyanasundaram, B., Pruhs, K.R.: Constructing compet itive tours from local in- formation. Theoretical Computer Science 130(1) (1994)

1994
[20]

In: Khuller, S., Williams, V.V

Karlin, A.R., Klein, N., Gharan, S.O.: A (slightly) impr oved approximation algo- rithm for metric TSP. In: Khuller, S., Williams, V.V. (eds.) STOC ’21:. pp. 32–45 (2021)

2021
[21]

Springer US (1972)

Karp, R.M.: Reducibility among Combinatorial Problems . Springer US (1972)

1972
[22]

Texts in Theoretical Computer Science

Komm, D.: An Introduction to Online Computation – Determ inism, Randomiza- tion, Advice. Texts in Theoretical Computer Science. An EAT CS Series, Springer (2016)

2016
[23]

Liu, F., Lu, C., Gui, L., Zhang, Q., Tong, X., Yuan, M.: Heu ris- tics for vehicle routing problem: A survey and recent advanc es (2023), https://arxiv.org/abs/2303.04147

2023 arXiv
[24]

In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing

Manasse, M., McGeoch, L., Sleator, D.: Competitive algo rithms for on-line prob- lems. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. p. 322–333. STOC ’88, Association for Computing Machinery, New York, NY, USA (1988)

1988
[25]

Theoretical Computer Science 463 (2012)

Megow, N., Mehlhorn, K., Schweitzer, P.: Online graph ex ploration: New results on old and new algorithms. Theoretical Computer Science 463 (2012)

2012
[26]

IEICE Trans

Miyazaki, S., Morimoto, N., Okabe, Y.: The online graph e xploration problem on restricted graphs. IEICE Trans. Inf. Syst. 92-D (2009) 16

2009
[27]

In: Advances in Neural Information Processing Syste ms

Purohit, M., Svitkina, Z., Kumar, R.: Improving online a lgorithms via ML predic- tions. In: Advances in Neural Information Processing Syste ms. Curran Associates, Inc. (2018)

2018
[28]

SIAM Journal on Computi ng 6(3) (1977)

Rosenkrantz, D.J., Stearns, R.E., Lewis, II, P.M.: An an alysis of several heuristics for the traveling salesman problem. SIAM Journal on Computi ng 6(3) (1977)

1977
[29]

In: Dis- crete Optimization, Handbooks in Operations Research and M anagement Science, vol

Schrijver, A.: On the history of combinatorial optimiza tion (till 1960). In: Dis- crete Optimization, Handbooks in Operations Research and M anagement Science, vol. 12, pp. 1–68 (2005)

2005
[30]

In: DeMillo, R.A

Sleator, D.D., Tarjan, R.E.: Amortized eﬃciency of list update rules. In: DeMillo, R.A. (ed.) Proceedings of the 16th Annual ACM Symposium on Th eory of Com- puting, April 30 - May 2, 1984, Washington, DC, USA. ACM (1984 ) 17

1984

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

In: Structural Information an d Communication Com- plexity - 31st International Colloquium, SIROCCO 2024

van den Akker, E., Buchin, K., Foerster, K.: Multi-agent o nline graph exploration on cycles and tadpole graphs. In: Structural Information an d Communication Com- plexity - 31st International Colloquium, SIROCCO 2024. Spr inger (2024)

work page 2024

[2] [2]

Algorithmica 29(4), 560–581 (2001)

Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.: Algorithms for the on-line travelling salesman. Algorithmica 29(4), 560–581 (2001)

work page 2001

[3] [3]

In: Proceedings of the 53rd Annual ACM SIGACT Symposiu m on Theory of Computing

Azar, Y., Leonardi, S., Touitou, N.: Flow time scheduling with uncertain processing time. In: Proceedings of the 53rd Annual ACM SIGACT Symposiu m on Theory of Computing. STOC 2021, Association for Computing Machine ry (2021)

work page 2021

[4] [4]

In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Azar, Y., Leonardi, S., Touitou, N.: Distortion-oblivio us algorithms for minimiz- ing ﬂow time. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM (2022)

work page 2022

[5] [5]

In: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Azar, Y., Peretz, E., Touitou, N.: Distortion-Oblivious Algorithms for Schedul- ing on Multiple Machines. In: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Schloss Dagstuhl – Leibniz-Zent rum für Informatik (2022)

work page 2022

[6] [6]

In: 31st Annual European Symposium on Algo rithms, ESA 2023

Baligács, J., Disser, Y., Heinrich, I., Schweitzer, P.: E xploration of graphs with excluded minors. In: 31st Annual European Symposium on Algo rithms, ESA 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023) 15

work page 2023

[7] [7]

In: 31st Annual European Symposium o n Algorithms (ESA 2023)

Bampis, E., Escoﬃer, B., Gouleakis, T., Hahn, N., Lakis, K ., Shahkarami, G., Xefteris, M.: Learning-Augmented Online TSP on Rings, Tree s, Flowers and (Al- most) Everywhere Else. In: 31st Annual European Symposium o n Algorithms (ESA 2023). vol. 274 (2023)

work page 2023

[8] [8]

Opera- tions Research 16(3), 538–558 (1968)

Bellmore, M., Nemhauser, G.L.: The traveling salesman pr oblem: A survey. Opera- tions Research 16(3), 538–558 (1968). https://doi.org/10.1287/opre.16.3.538

work page doi:10.1287/opre.16.3.538 1968