Approksimasjon utover polynomisk tid

Hvordan kan vi få bedre løsninger på problemer som er for vanskelige å løse eksakt? Madhumita Kundus avhandling utforsker dette spørsmålet ved å vise at hvis vi gir algoritmer litt mer tid, kan de ofte produsere løsninger som er langt nærmere det best mulige.

Mange beregningsproblemer i den virkelige verden er så komplekse at det er urealistisk å finne det perfekte svaret raskt. I stedet designer informatikere tilnærmingsalgoritmer som sikter mot løsninger som er «gode nok» og kommer med bevisbare garantier. Denne avhandlingen viser at ved å bevege seg utover det vanlige fokuset på svært raske algoritmer, er det mulig å oppnå løsninger av mye høyere kvalitet for et bredt spekter av vanskelige problemer.

Arbeidet samler ideer fra tilnærmingsalgoritmer, parameterisert kompleksitet og eksakte eksponensielle tidsalgoritmer for å bedre forstå avveiningen mellom kjøretid og løsningskvalitet. En del av avhandlingen utvikler generelle metoder for å designe algoritmer som, gitt mer tid, kan returnere stadig mer nøyaktige løsninger. Disse ideene brukes på grafsnittsproblemer, som oppstår når nettverk må deles effektivt, og også på et problem fra læringsteori som involverer sannsynlighetsmodeller.

En annen del av oppgaven studerer optimaliseringsproblemer med ytterligere strukturelle krav, spesielt tilkoblingsbegrensninger der løsninger må forbli koblet på spesifikke måter. Til tross for deres klassiske hardhet, viser den at effektive algoritmer fortsatt kan oppnå nesten optimale løsninger, og undersøker også hvordan man dekker problemer med kapasitetsgrenser, noe som gir sterke garantier i strukturerte settinger.

Alt i alt fremhever oppgaven et enkelt, men sterkt budskap: ved å tillate mer fleksible forestillinger om effektivitet og ved å utnytte skjult struktur, kan algoritmer oppnå vesentlig bedre løsninger på noen av databehandlingens vanskeligste problemer.

Personalia

Madhumita Kundu har vært doktorgradsstudent i gruppen for algoritmer og maskinlæring ved Institutt for informatikk, Universitetet i Bergen, siden desember 2020. Forskningen hennes veiledes av professor Pekka Parviainen, med professor Saket Saurabh som medveileder. Hun fullførte sin mastergrad i informatikk ved Indian Statistical Institute i Kolkata, India.