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

Apulaisprofessori Jukka Luoma. Kuva: Mikko Raskinen / Aalto-yliopisto
Tutkimus ja taide Julkaistu:

Ideologinen onttous auttaa kapitalismin voittoihin

Apulaisprofessori Jukka Luoma ja kollegansa löysivät yllättävän yhteyden organisaatio-oppimisen ja poliittisten taustaideologioiden väliltä.
DSC00431
Tutkimus ja taide Julkaistu:

Building 2030 tutki: Parempia rakennusprojekteja hajautetulla työnsuunnittelulla

Rakentamisessa on useita tapoja sujuvoittaa toteutusta, vähentää hukkaa ja tiivistää aikataulua. Building 2030 –konsortion rahoittama hanke tutki työmaata tukevan suunnittelun, hajautetun työnsuunnittelun ja tahtituotannon mahdollisuuksia ja vaikutuksia rakentamisessa. Tulosten ja kehitettyjen uusien menetelmien perusteella pienilläkin muutoksilla on suuri vipuvoima.
Small screenshot of takeout.aalto.fi
Kampus, Tutkimus ja taide, Opinnot Julkaistu:

Varaukset taas mahdollisia Takeoutin sivuilta

Varausten teko Studiosin ja Väreen lainaamoista on jälleen mahdollista Takoutin nettisivuston kautta .
Learning Centre graphics
Tutkimus ja taide, Opinnot, Yliopisto Julkaistu:

Uusi hakupalvelu Aalto-Primo on otettu käyttöön

Aalto-Finna on vaihtunut uuteen hakupalveluun Aalto-Primoon.