000199296 001__ 199296
000199296 005__ 20180913062523.0
000199296 020__ $$a978-0-7695-5135-7
000199296 0247_ $$2doi$$a10.1109/Focs.2013.35
000199296 02470 $$2ISI$$a000330672400027
000199296 037__ $$aCONF
000199296 245__ $$aNavigating Central Path with Electrical Flows: from Flows to Matchings, and Back
000199296 260__ $$bIEEE$$c2013$$aNew York
000199296 269__ $$a2013
000199296 300__ $$a10
000199296 336__ $$aConference Papers
000199296 490__ $$aAnnual IEEE Symposium on Foundations of Computer Science
000199296 520__ $$aWe 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.
000199296 6531_ $$amaximum flow problem
000199296 6531_ $$aminimum s-t cut problem
000199296 6531_ $$abipartite matchings
000199296 6531_ $$aelectrical flows
000199296 6531_ $$ainterior-point methods
000199296 6531_ $$acentral path
000199296 6531_ $$aLaplacian linear systems
000199296 700__ $$0246430$$g217799$$aMadry, Aleksander
000199296 7112_ $$aIEEE 54th Annual Symposium on Foundations of Computer Science (FOCS)
000199296 773__ $$t2013 IEEE 54th Annual Symposium on Foundations of Computer Science (Focs)$$q253-262
000199296 909C0 $$0252467$$pTHL1$$xU12584
000199296 909CO $$pconf$$ooai:infoscience.tind.io:199296
000199296 917Z8 $$x217799
000199296 937__ $$aEPFL-CONF-199296
000199296 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000199296 980__ $$aCONF