Matchings, Maximum Flow, and Matroid Intersections are fundamental combinatorial optimization problems that have been studied extensively since the inception of computer science. A series of breakthroughs in graph algorithms and continuous optimization in the past decade has led to exciting almost-optimal algorithms for maximum flow and bipartite matching. However, we are still far from fully understanding these problems. First, it remains open how to solve these problems in modern models of computation, such as parallel, dynamic, online, and communication models. Second, as algorithms become more sophisticated in pursuit of efficiency, they often sacrifice simplicity, potentially obscuring valuable combinatorial insights. This raises a fundamental question: can we develop efficient algorithms that maintain the combinatorial nature of these problems, rather than relying on linear algebra and continuous methods?

This thesis returns to the classic augmenting paths framework---the original approach to matchings, maximum flow, and matroid intersection---with the goal of developing new efficient combinatorial algorithms. Our key contributions include the first combinatorial algorithm achieving almost-linear time for maximum flow on dense graphs, and the first subquadratic independence-query algorithm for matroid intersection. For modern computational models, our contributions include an improved online rounding scheme for fractional matching (leading to an optimal online edge coloring algorithm), a resolution of the query and communication complexity for bipartite matching, and the first sublinear-round parallel algorithms for matroid intersection.

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.