Online graph exploration

Speaker(s)

Júlia Baligács

Language of the talk

English

Date

March 13, 2026, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

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. The goal is to find a good approximation for TSP despite the lack of information. A central question is whether a constant approximation factor can be achieved for all graphs. 

In this talk, I review the main results on this problem, including an algorithm achieving a constant approximation factor for minor-free graphs, and present a new lower bound of 4.

---