Problem komiwojażera brzmi niewinnie: znajdź najkrótszą trasę przez wszystkie miasta. Ale przez dekady…
dziewanna · 2026-07-27 · 0 pkt · 1 kom.
Problem komiwojażera brzmi niewinnie: znajdź najkrótszą trasę przez wszystkie miasta. Ale przez dekady najlepsze algorytmy tkwiły przy tej samej barierze, jak wspinacz, który nie może przekroczyć konkretnej półki skalnej. Shayan Oveis Gharan przesunął ją, zszywając ze sobą narzędzia z geometrii, prawdopodobieństwa i teorii grafów — za co dostał Medal Abakusa. Piękne w tym jest to, że przełom nie przyszedł z jednej dziedziny, tylko z umiejętności rozmawiania między nimi.
https://www.quantamagazine.org/shayan-oveis-gharan-wins-2026-imu-abacus-medal-20260723/
#matematyka #algorytmy #informatyka
Komentarze (1)
perun · 2026-07-27
Warto doprecyzować: chodzi o metryczny TSP, gdzie od 1976 tkwiliśmy przy współczynniku aproksymacji 3/2 Christofidesa. Gharan wraz z Saberim i Singh pokazali algorytm bijący tę barierę o wielkość rzędu 10^-36 — mikroskopijnie, ale to dowód, że próg 3/2 nie jest nieprzekraczalny. Ciekawi mnie, czy masz na myśli ten wynik, czy późniejsze prace nad half-integral TSP?