M.Sc. Andreas Grigorjew puollustaa väitöskirjaansa "Algorithms and Graph Structures for Splitting Network Flows, in Theory and Practice" keskiviikkona 19.2.2025 klo 13 Helsingin yliopiston Exactum-rakennuksen auditoriossa A111 (Pietari Kalmin katu 5, 1. kerros). Vastaväittäjänä toimii professori László A. Végh (Universität Bonn, Saksa) ja kustoksena apulaisprofessori Alexandru I. Tomescu (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Andreas Grigorjewin väitöskirja on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Algorithmic Bioinformatics -ryhmän Graph Algorithms -tiimissä tehtävää tutkimusta. Väitöskirjan ohjaajana on toiminut apulaisprofessori Alexandru I. Tomescu (Helsingin yliopisto).
Algoritmit ja verkon ominaisuudet verkkovuon osittamiseen teoriassa ja käytännössä
Virtaus suunnatuissa verkoissa (verkkovuo) mittaa yksiköitä, jotka liikkuvat verkon solmujen välillä. Käsitteellä voidaan mallintaa logistiikkaketjuja. Tyypillinen teema verkkoteoriassa on monimutkaisten objektien osittaminen yksinkertaisemmiksi, joita voidaan työstää riippumattomasti. Vaikka verkkovuota on tutkittu laajalti, virtauksen osittaminen on jäänyt vähemmälle huomiolle siitäkin huolimatta, että verkkovuon ja yleisimmin verkkojen osittaminen on relevanttia teoriassa ja myös käytännön sovelluksien kannalta.
Tässä tutkielmassa tarkastellaan minimaalista verkkovuon osittamista (engl. Minimum Flow Decomposition, MFD). Tässä MFD-ongelmassa etsitään pienintä joukkoa painotettuja polkuja, joiden yhdistelmä vastaa kokonaislukuarvoista virtausta. Tämä on perustavanlaatuinen NP-kova optimointiongelma, jolla on sovelluksia monilla tieteenaloilla, kuten bioinformatiikassa, tietoverkoissa ja logistiikkaketjujen suunnittelussa. Tämä työ keskittyy ongelman rajoitettuun tapaukseen, jossa verkko on syklitön (engl. directed acyclic graph, DAG) ja verkkovuo on kokonaislukuarvoinen. Työ sisältää sekä teoriaa että käytäntöä. Keskeisenä konseptina työssä on syklittömän verkon leveys (engl. DAG width) - pienin määrä polkuja, jotka kattavat kaikki kaaret.
Koska monet optimointiongelmat ovat NP-kovia, eikä niitä siksi voi ratkaista tarkasti monissa käytännön tapauksissa, on niiden ratkaisuun kehitetty heuristiikkoja kompromissiksi tarkkuuden ja ratkaisunopeuden välillä. Huolimatta aktiivisesta tutkimuksesta heurististen ratkaisujen parissa, MFD-ongelmasta on saavutettu vain vähäisessä määrin uutta teoreettista ymmärrystä. Tutkielman kolmessa ensimmäisessä artikkelissa tarkastellaan heuristiikkojen suhdetta verkon ominaisuuksiin. Tarkastelu johtaa kahden variantin erottamiseen: negatiivisten painojen salliminen ja painojen pakottaminen positiivisiksi. Ensimmäisessä tapauksessa saavutetaan approksimaatioalgoritmi, jolla on suoritustakuu kaikilla syötteillä. Jälkimmäisessä tapauksessa saavutetaan sama tulos, mutta rajoitettuna käytännön sovelluksissa tyypillisesti esiintyviin verkkoihin. Laskennan vaativuutta analysoidaan suhteessa syklittömän verkon leveyteen liittyviin käsitteisiin.
Tutkielman neljännessä artikkelissa käytetään kokonaislukuarvoista lineaarista ohjelmointia (engl. Integer Linear Programming, ILP) parantamaan MFD-ongelman sekä tarkkaa että heuristista ratkaisemista. Lähestymistapa parantaa nopeimman tunnetun tarkan ILP-ratkaisun suoritusaikaa käyttämällä esiprosessointia. Lisäksi tutkimuksessa kehitetään MFD:n uusi variantti ja näytetään, että sitä voidaan käyttää alkuperäisen ongelman approksimaatioon. Tällä saavutetaan selvästi parempi approksimaatiotakuu kuin aiemmilla heuristiikoilla siten, että suoritusaika pysyy kohtuullisena tutkimuksessa käytetyillä aineistoilla.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio tulee olemaan saatavilla Helsingin yliopiston avoimessa julkaisuarkistossa Heldassa osoitteessa http://urn.fi/URN:ISBN:978-952-84-0770-6.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: andreas.grigorjew@helsinki.fi.