Matchings, Maxflows, Matroids
The Power of Augmenting Paths and Computational Models
Tid: On 2024-11-27 kl 14.00
Plats: F3 (Flodis), Lindstedtsvägen 26 & 28, Stockholm
Språk: Engelska
Ämnesområde: Datalogi
Respondent: Joakim Blikstad , Teoretisk datalogi, TCS
Opponent: Professor Sanjeev Khanna, University of Pennsylvania
Handledare: Associate professor Danupon Na Nongkai, Teoretisk datalogi, TCS; Associate professor Per Austrin, Teoretisk datalogi, TCS
QC 20241105
Abstract
Matchningar, Maximala Flöden och Matroidsnitt är grundläggande kombinatoriska optimeringsproblem som har studerats ingående sedan datorvetenskapens början. En serie genombrott inom grafalgoritmik och kontinuerlig optimering under det senaste årentiondet har lett till imponerande nästan optimala algoritmer för maximalt flöde och bipartit matchning. Vi är dock fortfarande långt ifrån att fullt förstå dessa problem. För det första återstår frågan om hur man kan lösa dessa problem i andra beräkningsmodeller, såsom parallell-, dynamisk-, online- och kommunikationsmodeller. För det andra, när algoritmer blir allt mer sofistikerade i deras effektivitetsträvan, offrar de ofta enkelhet, vilket potentiellt kan dölja värdefulla kombinatoriska insikter. Detta motiverar en grundläggande fråga: kan vi utveckla effektiva algoritmer som bevarar den kombinatoriska karaktären hos dessa problem, istället för att förlita sig på linjär algebra och kontinuerliga metoder?
Denna avhandling återgår till de klassiska augmenting-pathsalgoritmerna---det ursprungliga angreppssättet för matchningar, maximalt flöde och matroid-snitt---med målet att utveckla nya effektiva kombinatoriska algoritmer. Våra viktigaste bidrag inkluderar den första kombinatoriska algoritmen som uppnår nästan linjär tid för maximalt flöde på täta grafer, och den första subkvadratiska independence-query-algoritmen för matroidsnitt. För moderna beräkningsmodeller inkluderar våra bidrag förbättrade onlineavrundningsalgorithmer för fraktionell matchning (vilket leder till en optimal onlinealgoritm för kantfärgning), en lösning av query- och kommunikationskomplexiteten för bipartit matchning, och de första sublinjära parallella algoritmerna för matroidsnitt.