28 października 2024 11:43
Postęp w zrozumieniu drzewa Steinera - praca J. Byrki na FOCS 2024
Praca Jarosława Byrki, Fabrizio Grandoniego i Very Traub The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2 została przyjęta na FOCS’24 - jedną z najbardziej prestiżowych konferencji informatycznych na świecie.
Postęp w zrozumieniu drzewa Steinera
Jednym z klasycznych problemów optymalizacyjnych jest: Jak najtaniej połączyć zadany podzbiór wierzchołków danego grafu? W znajdowaniu jak najlepszych rozwiązań pomagają programy liniowe, które modelują wybór odpowiedniego podzbioru krawędzi.
Najprostszy z nich: UCR (ang. Undirected Cut Relaxation) ma po prostu zmienne na krawędziach i wiadomo o nim, że jest słaby (jako metoda szacowania kosztu rozwiązania optymalnego). Najsilniejszy, HYP (ang. Hypergraphic), ze zmiennymi na podzbiorach wierzchołków do połączenia jest dokładniejszy ale, ze względu na bardzo dużą liczbę zmiennych, niezbyt praktyczny. Nadzieją jest program pośredni, BCR (ang. Bidirected Cut Relaxation) ze zmiennymi na skierowanych krawędziach, który jest szybki ale nie wiadomo o nim jak bardzo może być niedokłady.
We współpracy z Prof. Fabrizio Grandoni (Lugano, Szwajcaria) i Prof. Vera Traub (Bonn, Niemcy), udało nam się po raz pierwszy pokazać, że BCR jest istotnie silniejszy od UCR. Odkrycie to rodzi nadzieję, że w przyszłości powstaną efektywne algorytmy prymalno-dualne w oparciu o BCR.
