Aallon tutkijat palkittiin artikkelista, joka osoittaa, ettei pariutusongelmaa voi ratkaista nykyistä tehokkaammin

Arvostettu Foundations of Computer Science (FOCS 2019) -konferenssi on myöntänyt parhaan tutkimusartikkelin palkinnon Aalto-yliopiston tietotekniikan laitoksen apulaisprofessori Jukka Suomelalle ja hänen kollegoilleen. FOCS on teoreettisen tietojenkäsittelytieteen alalla maailman kahden tärkeimmän konferenssin joukossa.

Palkitun artikkelin otsikko on Lower bounds for maximal matchings and maximal independent sets. Se käsittelee pariutusongelmaa, joka on kiinnostanut alan tutkijoita jo pitkään.

Tietojenkäsittelytieteessä perustavanlaatuinen kysymys on, mitä kaikkea voi automatisoida tehokkaasti. Tutkimuksessaan Suomelan työryhmä tarkasteli asiaa hajautetun laskennan näkökulmasta ja pohti, mitä kaikkea tietoverkossa voi ratkaista tehokkaasti. ”Pariutusongelma on yksi esimerkki tämän tyyppisestä kysymyksestä”, Suomela sanoo.

Siinä keskeistä on, miten kauas tietoverkon yksittäisestä solmusta täytyy nähdä, jotta solmulle löytyisi pari. Suomelan ja hänen tutkijakollegoidensa tutkimus osoittaa matemaattisesti, että verkossa pelkästään lähiympäristöön katsominen ei riitä: pariutusongelmaa ei voi ratkaista nykyisiä algoritmeja tehokkaammin.

Vaikka kyse on teoreettisesta perustutkimuksesta, pariutusongelmaa voi havainnollistaa yksinkertaistetusti tilanteella, jossa työnantajat tarvitsevat uusia työntekijöitä ja työnhakijat uuden työpaikan. Työnantajan täytyy siis löytää itselleen pari ja päinvastoin. Ongelman voi ratkaista keskitetysti hyödyntämällä työvoimatoimiston kaltaista keskitettyä palvelua, jossa on tieto kaikista työnhakijoista ja avoimista työpaikoista.

Toinen keino on ratkaista ongelma hajautetusti tai paikallisemmin. Esimerkissä työnhakija listaisi kaikki häntä kiinnostavat työpaikat ja lähestyisi niitä systemaattisesti yksi kerrallaan. Tällainen menetelmä on kuitenkin hidas, joten alan tutkijoita on pitkään kiinnostanut, miten tehokkaasti algoritmit voivat ratkaista tehtävän.

Suomela kollegoineen todistaa artikkelissaan, että mikä tahansa pariutusongelman ratkaiseva menetelmä on joko hidas tai johtaa väistämättä väärään ratkaisuun. Tällaisia ongelmia ratkaisevien algoritmien kehitys alkaa siis olla siinä pisteessä, jossa voidaan todistaa tiettyjen menetelmien olevan parhaita tai lähes parhaita mahdollisia.

”Pystyimme tutkimuksessa asettamaan rajoja sille, miten tehokkaita menetelmiä voi olla olemassa. Saimme esimerkiksi selville, että eräs, vuodelta 2001 oleva menetelmä on joissain tilanteissa paras mahdollinen. Sitä ei pysty enää aidosti nopeuttamaan”, Suomela sanoo.

Tutkimusprojektissa olivat mukana Aallon tutkijatohtorit Alkida Balliu, Juho Hirvonen, Dennis Olivetti ja Mikaël Rabie sekä sveitsiläisen ETH Zurichin tutkijatohtori Sebastian Brandt. Tutkimusta on rahoittanut Suomen Akatemia.

Työryhmän saama palkinto on yksi teoreettisen tietojenkäsittelytieteen alan arvostetuimmista. ”On erittäin epätodennäköistä, että toista kertaa omalla urallani jotain yhtä isoa tulee vastaan”, Suomela sanoo. ”Alalla on ehkä viisi juttua, joista kaikki puhuvat tänä vuonna. Tämä on yksi niistä. Itselleni tämä merkitsee todella, todella paljon.”

Vuosittain järjestettävä FOCS-konferenssi pidetään tänä vuonna Baltimoressa, Yhdysvalloissa 9.–12. marraskuuta.

Linkki tutkimusartikkeliin: https://arxiv.org/abs/1901.02441

Lue myös Suomelan blogikirjoitus aiheesta