199296
20180913062523.0
978-0-7695-5135-7
10.1109/Focs.2013.35
doi
000330672400027
ISI
CONF
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
New York
2013
IEEE
2013
10
Conference Papers
Annual IEEE Symposium on Foundations of Computer Science
We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) running time bound due to Even and Tarjan [16]. By well-known reductions, this also establishes an O(m^10/7)-time algorithm for the maximum-cardinality bipartite matching problem. That, in turn, gives an improvement over the celebrated O(mn^1/2) running time bound of Hopcroft and Karp [25] whenever the input graph is sufficiently sparse. At a very high level, our results stem from acquiring a deeper understanding of interior-point methods - a powerful tool in convex optimization - in the context of flow problems, as well as, utilizing certain interplay between maximum flows and bipartite matchings.
maximum flow problem
minimum s-t cut problem
bipartite matchings
electrical flows
interior-point methods
central path
Laplacian linear systems
Madry, Aleksander
217799
246430
IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS)
253-262
2013 IEEE 54th Annual Symposium on Foundations of Computer Science (Focs)
THL1
252467
U12584
oai:infoscience.tind.io:199296
conf
217799
EPFL-CONF-199296
EPFL
PUBLISHED
REVIEWED
CONF