Kuulin juuri, että artikkelimme “Lower bounds for maximal matchings and maximal independent sets” sai erittäin arvostetun Foundations of Computer Science (FOCS 2019) -konferenssin parhaan artikkelin palkinnon, ja ajattelin kirjoittaa laajemmalle yleisölle, mistä työssä on kyse.

Tarina alkaa suunnilleen vuodesta 2011, kun olin tutkijatohtorina Helsingin yliopiston tietojenkäsittelytieteen laitoksella. Tutkin hajautetun laskennan perusteita: mitä on mahdollista laskea tehokkaasti laajassa tietoverkossa, ja mitä ongelmia taas on mahdotonta ratkaista nopeasti. Törmäsimme harmittoman oloiseen pieneen pähkinään, joka tuntui odottavan ratkaisua: pariutusten löytäminen.

Pariutusongelma

Ongelma on helpointa selittää, kun unohdetaan tietokoneet ja ajatellaan (reippaasti yksinkertaistettua) tosielämän tilannetta, jossa toimijoina ovat ihmiset. Otetaan esimerkiksi työnhakutilanne: meillä on iso joukko ihmisiä etsimässä työpaikkaa ja iso joukko avoimia tehtäviä, ja kukin ihminen on kiinnostunut tietyistä tehtävistä. Kaisaa kiinnostaa työpaikat A, B ja C ja Liisaa taas työpaikat A, C, D ja E, jne. Pidetään tämä niin yksinkertaisena kuin mahdollista ja ajatellaan, että Kaisalle ei ole väliä, saako työpaikan A, B vai C, ja työnantajalle A ei ole väliä, saako hän töihin Kaisan vai Liisan. Miten löydetään pariutus työnhakijoiden ja työpaikkojen välille?

Yksi lähestymistapa on keskitetty ratkaisu, tutummin työvoimatoimisto: kerätään tieto kaikista työpaikoista ja työnhakijoista yhteen paikkaan ja etsitään pariutus näiden välillä. Mutta voiko ongelman ratkaista hajautetusti, niin, että kukin työnhakija on yhteydessä ainoastaan niihin työnantajiin, joista on kiinnostunut? Ja miten tämä onnistuisi nopeasti pelkästään sähköposteja lähettämällä?

Hidas hajautettu ratkaisu

Hyvin yksinkertainen ratkaisu on tämä:

• Kukin työnhakija laittaa hakemuksen oman listansa ensimmäiselle työnantajalle. Kaisa lähettää sähköpostia työpaikkaan A, niin myös Liisa.
• Työnantajat, jotka saivat hakemuksia, hyväksyvät niistä yhden ja hylkäävät muut. Kaisa saa paikan A, Liisa taas saa sähköpostiinsa huonoja uutisia.
• Tämän jälkeen kaikki työnhakijat, jotka ovat edelleen ilman työtä, laittavat hakemuksen oman listansa seuraavalle työnantajalle. Liisa lähettää sähköpostia työpaikkaan C ja jää odottamaan vastausta sieltä.

Työntekijät käyvät tähän tapaan omaa listaansa läpi, laittavat postia yhdelle työnantajalle, odottavat vastausta ja siirtyvät sitten seuraavaan. Jotkut työntekijät voivat jäädä ilman työtä, mutta löydetty pariutus työntekijöiden ja työpaikkojen välillä on ainakin maksimaalinen: jos esimerkiksi Liisa jää lopulta ilman työtä, kaikki häntä kiinnostavat työpaikat on jo täytetty.

Haittapuolena on kuitenkin menetelmän hitaus: jos olen kiinnostunut sadasta työpaikasta ja vastauksen saaminen yhteen sähköpostiin vie keskimäärin päivän, voin pahimmillaan joutua odottamaan sata päivää, että löydän listaltani työpaikan.

Voisiko tämän tehdä jotenkin paljon nopeammin? Olisiko olemassa jokin nokkela menetelmä, joka säästäisi aikaa?

Mahdottomuustulosta etsimässä

Samantyylisiä ongelmia on tarkasteltu alan tutkimuskirjallisuudessa jo 1980-luvulta alkaen, mutta mitään nopeampaa menetelmää ei tunneta: kaikki hajautetut algoritmit maksimaalisen pariutuksen löytämiseen ovat pahimmassa tapauksessa aivan yhtä hitaita kuin yllä kuvattu helppo menetelmä.

Olisiko mahdollista, että tuo hyvin yksinkertainen menetelmä pariutuksen löytämiseen on sittenkin paras mahdollinen? Voisiko tämän todistaa matemaattisesti?

Aloimme tutkia tätä meidän tutkimusryhmässämme vuoden 2011 tienoilla. Lupaavia osittaisia tuloksia julkaisimme alan konferensseissa jo vuonna 2012, mutta läpimurto jäi saavuttamatta.

Ongelma pysyi kuitenkin koko ajan mielessä. Vuonna 2014 aloitin Aalto-yliopiston tietotekniikan laitoksella apulaisprofessorina, ja vuonna 2015 saimme Suomen Akatemialta rahoitusta pariutusongelmaan liittyvään tutkimushankkeeseen. Lähes aina kun tapasin kollegoita, otin pariutusongelman esiin yhtenä avoimena ongelmana. Kukaan alan tutkijoista ei kuitenkaan keksinyt, miten ongelmaa voisi lähestyä.

Läpimurtoviikko

Sveitsiläinen tutkijatohtori Sebastian Brandt oli käymässä tutkimusvierailulla Aallossa joulukuussa 2018. Sebastianilla oli kiinnostava uusi tulos, jota hänen oli tarkoitus esitellä meille.

Kuten niin monta kertaa aiemminkin, keskustelu ajautui sivuraiteille — aloimme miettiä pariutusongelmaa. Voisiko Sebastianin kehittämä uusi todistustekniikka sopia tähänkin? Tuntui lupaavalta, mutta työ edistyi hitaasti: jokainen yritys tuntui johtavan siihen, että teemme valkotaulun ääressä työläitä ja hankalia laskelmia monta tuntia ja lopulta toteamme, että tämäkin oli taas yksi umpikuja.

Tutkimusryhmässämme työskentelevä italialainen tutkijatohtori Dennis Olivetti keksi automatisoida ison osan mekaanisesta työstä. Dennisin yhdessä illassa kirjoittaman tietokoneohjelman avulla pystyimme nopeasti testaamaan erilaisia hypoteeseja. Intensiivisen viikon loppuun mennessä meillä oli niin hyvä ymmärrys ongelmasta, että yhteistyönä pystyimme keksimään, miten todistus viedään kokonaisuudessaan maaliin — mukana oli Sebastianin, Dennisin ja minun lisäksi Aallosta tutkijatohtorit Alkida Balliu, Mikaël Rabie ja Juho Hirvonen.

Todistusideasta on vielä pitkä matka huolellisesti kirjoitettuun tieteelliseen artikkeliin. Tiesimme, että meillä on käsissä läpimurtotulos, mutta ehdimmekö julkaista sen ennen kuin joku muu tutkimusryhmä ratkaisee saman ongelman? Joululomat olivat tulossa; itse kirjoittelin käsikirjoitusta junassa matkalla sukulaisten luo joulun viettoon. Lopulta 8. tammikuuta 2019 kaikki palaset olivat koossa: julkaisimme arXiv-verkkopalvelussa käsikirjoituksen, jossa todistetaan, että pariutusongelmaan ei ole olemassakaan tehokkaampaa ratkaisua. Mikä tahansa menetelmä, joka ratkaisee pariutusongelman, on joko hidas tai johtaa väistämättä väärään ratkaisuun (esim. pariutus ei ole maksimaalinen).

Lisätietoja

Sähköpostiosoitteeni löytyy kotisivultani; minuun voi hyvin ottaa yhteyttä myös esim. Twitterissä. Luennoin Aalto-yliopistossa joka syksy kurssin Distributed Algorithms, jolla voi tutustua paljon tarkemmin siihen, miten hajautettuja algoritmeja ja niitä koskevia mahdottomuustuloksia voidaan tutkia.