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

Lue lisää uutisia

AI-generated colourful images of robot-looking figures and humans programming.
Tutkimus ja taide Julkaistu:

Ohjelmoinnin sietämätön keveys – tekoälyavusteinen koodaus pakottaa miettimään tietotekniikan opetuksen uudelleen

Aalto-yliopiston tietoteknisen opetuksen tutkijat osoittivat tutkimuksessaan, että tekoälyavusteinen ohjelmointi voi olla hyödyllinen työkalu opettajille.
An illustrated book with model wearing summery outfit lays on colourful textiles surface
Tutkimus ja taide, Opinnot Julkaistu:

DIALOGUES-näyttely tekstiilien tulevaisuudesta Dipolin galleriassa

Näyttelyssä on esillä Aalto yliopiston tekstiiliin liittyviä tutkimusprojekteja ja opiskelijatöitä.
A person wearing a shirt that says "build like an entrepreneur" sitting in class, in front of a drawing
Tutkimus ja taide Julkaistu:

Tutki taiteen ja yrittäjyyden yhtymäkohtia Aallon opiskeljoiden näyttelyssä

Art, Life and Entrepreneurship -kurssin lopputyöt ovat näytillä Väreen aulassa 29.11.–13.12.
Andrea Sand
Mediatiedotteet, Tutkimus ja taide Julkaistu:

Piille löytyy elektroniikassa lupaavia haastajia, mutta niiden säteilynkestävyys on arvoitus – tutkimusprojekti kehittää tehokasta tapaa säteilyvaurioiden ennustamiseen

Aalto-yliopiston apulaisprofessori Andrea Sand sai Euroopan tutkimusneuvostolta merkittävän rahoituksen puolijohteiden säteilyvaurioiden ennustamiseen. Uusi menetelmä voi avata ovia seuraavan sukupolven materiaalien käyttöönotolle.