Nasz informatyk na konferencji z noblistą!
Rozmawiamy z prof. dr. hab. Jarosławem Byrką z Instytutu Informatyki UWr, który pod koniec października uczestniczył w prestiżowej konferencji FOCS 2024 w Chicago, prezentując swoją pracę pn. The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2.
Jak dużą rangę ma konferencja FOCS i kogo gromadzi?
Konferencja FOCS jest jedną z dwóch flagowych konferencji informatycznych na świecie, drugą z nich jest konferencja STOC. Prezentowane są tam najważniejsze wyniki naukowe z tej dziedziny awydarzenie przyciąga badaczy z czołowych uczelni w USA. Warto zauważyć, że z polskich ośrodków naukowych jedynie badacze z UW, UWr, i czasami z UJ mają okazję zaprezentować tam swoje wyniki. Znaczenie tych konferencji dla informatyki można porównać do znaczenia czasopism Nature i Science dla nauk eksperymentalnych.
Czego dotyczy praca, którą tam Pan zaprezentował?
Artykuł dotyczy 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.
Jakie osobistości ze świata nauki udało się Panu spotkać?
Wśród prelegentów był m. in. Prof. Roger Myerson zdobywca Nagrody Nobla z Ekonomii w 2007 roku współtwórca współczesnej (ekonomicznej i algorytmicznej) teorii gier. Na konferencji obecni byli także inni światowej sławy badacze, jak chociażby Irit Dinur, z Weizmann Institute, Christos Papadimitriou z Columbia University czy Rajeev Alur z University of Pennsylvania.
Jakie tematy dominowały na tegorocznej konferencji?
Można zaobserwować, że coraz większą popularnością cieszą się tematy związane z możliwością prowadzenia obliczeń na komputerach kwantowych oraz wszelkie probabilistyczne argumenty dotyczące przetwarzania dużych
zbiorów danych.
Opr. E. Kośmider, za: Instytut Informatyki UWr
