Uutiset

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

Apulaisprofessori Jukka Suomela kollegoineen todistaa artikkelissaan matemaattisesti, että mikä tahansa pariutusongelman ratkaiseva menetelmä on joko hidas tai johtaa väistämättä väärään ratkaisuun.
Jukka Suomela Research Group
Palkitun artikkelin kirjoittaneessa työryhmässä olivat mukana Aallon tutkijatohtorit Juho Hirvonen (vas), Alkida Balliu ja Dennis Olivetti sekä apulaisprofessori Jukka Suomela.

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

  • Julkaistu:
  • Päivitetty:
Jaa
URL kopioitu

Lisää tästä aiheesta

Kuvassa kädet ja post-it-lappuja. Kuva: Adolfo Vera
Tutkimus ja taide Julkaistu:

Miten koronavirus on vaikuttanut yritysten strategioihin? – Kyselytutkimuksella tuotetaan tietoa päätöksenteon tueksi

Aalto-yliopiston hankkeessa tuotettu tieto auttaa yrityksiä, kun ne tekevät strategia- ja investointipäätöksiä.
PoP Pekka Mattila Taloudenpuolustuksen ensiapukurssilla 24.9.2020. Kuva: Kati Kiviniemi / Aalto EE
Tutkimus ja taide Julkaistu:

Operatiivisesti ketterät yritykset pärjäävät myös kriisin jälkeen

Tulevaisuuden menestysyrityksen tulee onnistua palauttamaan merkityksen tuntu.
UNITE! workshop at Aalto University in February 2020. Photo: Mikko Raskinen.
Tutkimus ja taide Julkaistu:

Tekniikan alan yliopistojen EU-hankkeessa luodaan tulevaisuuden yliopistoa

Tulevaisuuden yliopistossa kampuksesta tulee avoin kokeellinen laboratorio, virtuaalinen vaihto-opiskelija voi valita kursseja kaikkien yliopistojen tarjonnasta, ja yliopiston jokainen työntekijä kokee asiakseen toimia tasa-arvoa edistävällä tavalla.
Kuva: Adolfo Vera.
Tutkimus ja taide Julkaistu:

HUSissa ja Aallossa alkaa tutkimus EEG-aivosähkökäyrästä tehtävästä koronavirusinfektion hengitysvaikeuden ennusteesta

Koronaviruspotilaiden vakavien hengitysvaikeuksien taustatekijöitä etsitään koneoppimisen avulla EEG-aivosähkökäyristä. Tutkimuksen tuloksia on tarkoitus hyödyntää muidenkin potilaiden tehohoidon arvioinnissa.