Online graph exploration

Prelegent(ci)

Júlia Baligács

Język referatu

angielski

Termin

13 marca 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

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.

---