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:

Lue lisää uutisia

Ursula von der Leyen pitämässä avajaispuhetta
Yhteistyö, Tutkimus ja taide Julkaistu:

New European Bauhaus -festivaali toi yhteen Euroopan päättäjiä ja monialaisen kestävän kehityksen asiantuntijoita

Aalto-yliopisto oli mukana New European Bauhaus -festivaalilla kestävää rakentamista käsittelevällä näyttelyllään Time out! Rethinking construction.
Olli Ikkana in Otaniemi, photo by Lasse Lecklin.
Tutkimus ja taide Julkaistu:

Bioinspiroituja värejä ja olosuhteisiin sopeutuvia materiaaleja – Professori Olli Ikkalan kolmas EU-hanke pohjaa eläviin systeemeihin

Teknillisen fysiikan professori Olli Ikkala on saanut kolmannen kerran Euroopan tutkimusneuvoston Advanced Grant -rahoituksen. Rahoituksen suuruus on 2,5 miljoonaa euroa, ja hanke kestää viisi vuotta.
Professori Antti Oulasvirta. Kuva: Aalto-yliopisto / Jaakko Kahilaniemi
Mediatiedotteet, Tutkimus ja taide Julkaistu:

Tutkijat selvittävät, miten tekoäly saadaan ymmärtämään ihmistä paremmin

Antti Oulasvirta on saanut 2,5 miljoonan euron Euroopan tutkimusneuvoston Advanced Grant -rahoituksen käyttäjämallien tutkimiseen.
Kuvituskuva, jossa kirkkain värein piirretty tyttö katsoo graafista kuviota.
Tutkimus ja taide Julkaistu:

Suomen kaksivuotisen esiopetuskokeilun toteutus voi toimia mallina maailmalle

Kaksivuotisen esiopetuksen kokeilu on erinomainen esimerkki siitä, miten hallitukset voivat ennakoida ja testata politiikkaansa ennen sen laajamittaista käyttöönottoa. Suomi on kokeiluille mitä otollisin paikka.