Vi presenterar en O(m 10 7 ) = O(m 1.43 )-tid 1 algoritm för maximal s-t flöde och minsta s-t skär problem i riktade grafer med enhet kapacitet. Detta är den första förbättringen jämfört med det sparse-graf fallet av den långvariga O(m min{ ε m, n 2/3 }) körtid bunden på grund av Even och Tarjan [16]. Genom välkända minskningar, etablerar detta också en O(m 10 7 )-tidsalgoritm för maximal kardinalitet bipartite matchande problem. Detta ger i sin tur en förbättring jämfört med den berömda O(m ε n) körtid gränsad till Hopcroft och Karp [25] när inmatningskurvan är tillräckligt sparsam. På en mycket hög nivå, våra resultat härrör från att få en djupare förståelse av interiör-punkt metoder - ett kraftfullt verktyg i konvex optimering - i samband med flödesproblem, samt att utnyttja vissa samspel mellan maximala flöden och bipartite matchningar.
För glesa grafer, den första förbättringen på 40 år är Õ(m 10 7 ) tid algoritm på grund av Madry REF.
Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back
{'venue': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'journal': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}