Europejska Rada ds. Badań Naukowych (ERC) ogłosiła laureatów prestiżowych grantów przyznawanych młodym naukowcom, którzy prowadzą pionierskie i przełomowe badania. Jednym z nich jest dr Michał Pilipczuk z Wydziału Matematyki, Informatyki i Mechaniki UW. W projekcie BOBR, wraz ze swoim zespołem, będzie badał strukturalne i dekompozycyjne własności sieci i próbował ich użyć do stworzenia szybkich metod obliczeniowych do rozwiązywania trudnych problemów.

Dr Michał Pilipczuk i dr Wojciech Czerwiński z Instytutu Informatyki UW otrzymali granty ERC. Przyznając Starting Grants, rada wspiera prowadzących przełomowe i odkrywcze projekty młodych naukowców, po 2-7 latach od obrony pracy doktorskiej.

Dowodząc twierdzeń

Jak rozwiązywać trudne problemy za pomocą szybkich metod obliczeniowych? Tym będzie się zajmował zespół badawczy dr. Michała Pilipczuka, który otrzymał grant Europejskiej Rady ds. Badań. W projekcie BOBR „Decomposition methods for discrete problems” naukowcy będą badali strukturalne i dekompozycyjne własności sieci.

Dr Michał Pilipczuk zajmuje się algorytmiką, czyli rozwiązywaniem różnego rodzaju problemów obliczeniowych głównie na grafach.

– Grafy to matematyczne modele sieci. Wyobraźmy sobie sieć drogową w Polsce – wierzchołkami grafów będą np. miasta, a krawędziami połączenia między nimi. Chcielibyśmy postawić 100 nowych szpitali i zrobić to w taki sposób, aby zminimalizować średni czas dojazdu do pacjenta. Musimy wziąć pod uwagę, że istnieją już pewne szpitale i drogi. Taki problem w ogólności jest trudny, nie wiemy jak go szybko rozwiązywać – mówi dr Michał Pilipczuk.

Laureat Starting Grant podobny problem rozpatruje na gruncie norweskim. – Wydaje się, że w Norwegii moglibyśmy szybciej wymyślić, gdzie należałoby wybudować te placówki. Moglibyśmy np. podzielić Norwegię na pół, niezależnie zdecydować o położeniu szpitali na południu i na północy kraju, a potem ewentualnie wprowadzić zmiany w okolicy cięcia – chcielibyśmy, żeby to była mała poprawka – dodaje.

Dr Pilipczuk wskazuje, że znalezienie małego separatora sieci drogowej w Norwegii i próba rozwiązania problemu poprzez podzielenie tej sieci małymi separatorami oraz poskładanie rozwiązań z mniejszych kawałków to podejście strukturalne. Naukowiec tłumaczy, że sieć drogowa w Norwegii ma niską szerokość drzewiastą – wygląda jak drzewo. Sieć drogowa w Polsce ma inną strukturę, jest bardziej płaska, bardziej kwadratowa i nie ma małych separatorów. Dzięki strukturalnej mierze takiej jak szerokość drzewiasta można odróżnić przypadki trudne takie jak Polska od przypadków łatwych – np. Norwegii.

Projekt „Decomposition methods for discrete problems” ma charakter teoretyczny. Naukowcy będą próbować zrozumieć matematyczną rzeczywistość, opisać ją. – Chcielibyśmy zrozumieć złożoność tych problemów, sklasyfikować je. Tego typu matematyczne myślenie może się przekuć w przyszłości na rozwiązania bardziej praktyczne – tłumaczy nagrodzony przez ERC informatyk.

W projekcie BOBR dr Michał Pilipczuk będzie zajmował się zastosowaniem strukturalnej teorii grafów w czterech obszarach dotyczących: teorii grafów rzadkich, parametryzowanych algorytmów dynamicznych, algorytmów na grafach planarnych oraz algorytmów na grafach z zabronionymi podstrukturami.

ERC przyznała na realizację przedsięwzięcia prawie 1,4 mln euro. Przy projekcie w ciągu 5 lat będzie pracować kilku doktorantów, badacze na stanowiskach typu postdoc oraz naukowcy z WMIM.