The maximum flow problem (or max flow) is, roughly speaking, to calculate the maximum amount of items that can move from one end of a network to another, given the capacity limitations of the network’s links. The items could be data packets traveling over the Internet or boxes of goods traveling over the highways; the links’ limitations could be the bandwidth of Internet connections or the average traffic speeds on congested roads.
Max flow (and its dual, the minimum s-t cut problem) is one of the most fundamental and extensively studied problems in computer science (and operations research and optimization) and a staple of introductory courses on algorithms. For decades it was a prominent research subject, with new algorithms that solved it more and more efficiently coming out once or twice a year. But as the problem became better understood, the pace of innovation slowed. Now, however, Jonathan Kelner, MIT assistant professor of applied mathematics, CSAIL grad student Aleksander Madry, math undergrad Paul Christiano, and Yale Professor Daniel Spielman and USC Professor Shanghua Teng, have demonstrated the first improvement of the max-flow algorithm in 10 years.
More technically, the problem has to do with what mathematicians call graphs. A graph is a collection of vertices and edges, which are generally depicted as circles and the lines connecting them. The standard diagram of a communications network is a graph, as is, say, a family tree. In the max-flow problem, one of the vertices in the graph — one of the circles — is designated the source, where the item comes from; another is designated the drain, where the item is headed. Each of the edges — the lines connecting the circles — has an associated capacity, or how many items can pass over it.
Such graphs have direct applications modeling real-world transportation and communication networks in a fairly straightforward way, but their applications are actually much broader. Max flow is the fastest algorithm right now for solving most optimization problems, often used as subroutines in other algorithms. Outside of network analysis, a short list of applications that use max flow include airline scheduling, circuit analysis, task distribution in supercomputers, digital image processing, and DNA sequence alignment.
Graphs to grids
Traditionally, algorithms for calculating max flow would consider one path through the graph at a time. If it had unused capacity, the algorithm would simply send more items over it and see what happened. Improvements in the algorithms’ efficiency came from cleverer and cleverer ways of selecting the order in which the paths were explored.
But Kelner and colleagues treat a capacitated, undirected graph as a network of resistors and describe a fundamentally new technique for approximating the maximum flow in these graphs by computing electrical flows in resistor networks. They then use this technique to develop the asymptotically fastest-known algorithm for solving the max flow problem by solving a sequence of electrical flow problems with varying resistances on the edges. Each of these electrical flow problems can be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time.
By representing the graph as a matrix, where each node in the graph is assigned one row and one column of the matrix and the number value where one node represented by a row and another node represented by a column intersect represents the capacity for transferring items between those two nodes. In the branch of mathematics known as linear algebra, a row of a matrix can also be interpreted as a mathematical equation, and the tools of linear algebra enable the simultaneous solution of all the equations embodied by all of a matrix’s rows. By repeatedly modifying the numbers in the matrix and re-solving the equations of the Laplacian system, the researchers effectively evaluate the whole graph at once, which turns out to be more efficient than trying out paths one by one.
If V is the number of vertices in a graph, and E is the number of edges between them, then the execution of the fastest previous max-flow algorithm was proportional to (V + E)^(3/2). The execution of the new algorithm is proportional to (V + E)^(4/3). For a network like the Internet, which has hundreds of billions of nodes, the new algorithm could solve the max-flow problem hundreds of times faster than its predecessor. In addition to the immediate practical use of the algorithm, its breakthrough approach will likely cause a paradigm shift in a number of fields and their approach to related problems.
Max flow (and its dual, the minimum s-t cut problem) is one of the most fundamental and extensively studied problems in computer science (and operations research and optimization) and a staple of introductory courses on algorithms. For decades it was a prominent research subject, with new algorithms that solved it more and more efficiently coming out once or twice a year. But as the problem became better understood, the pace of innovation slowed. Now, however, Jonathan Kelner, MIT assistant professor of applied mathematics, CSAIL grad student Aleksander Madry, math undergrad Paul Christiano, and Yale Professor Daniel Spielman and USC Professor Shanghua Teng, have demonstrated the first improvement of the max-flow algorithm in 10 years.
More technically, the problem has to do with what mathematicians call graphs. A graph is a collection of vertices and edges, which are generally depicted as circles and the lines connecting them. The standard diagram of a communications network is a graph, as is, say, a family tree. In the max-flow problem, one of the vertices in the graph — one of the circles — is designated the source, where the item comes from; another is designated the drain, where the item is headed. Each of the edges — the lines connecting the circles — has an associated capacity, or how many items can pass over it.
Such graphs have direct applications modeling real-world transportation and communication networks in a fairly straightforward way, but their applications are actually much broader. Max flow is the fastest algorithm right now for solving most optimization problems, often used as subroutines in other algorithms. Outside of network analysis, a short list of applications that use max flow include airline scheduling, circuit analysis, task distribution in supercomputers, digital image processing, and DNA sequence alignment.
Graphs to grids
Traditionally, algorithms for calculating max flow would consider one path through the graph at a time. If it had unused capacity, the algorithm would simply send more items over it and see what happened. Improvements in the algorithms’ efficiency came from cleverer and cleverer ways of selecting the order in which the paths were explored.
But Kelner and colleagues treat a capacitated, undirected graph as a network of resistors and describe a fundamentally new technique for approximating the maximum flow in these graphs by computing electrical flows in resistor networks. They then use this technique to develop the asymptotically fastest-known algorithm for solving the max flow problem by solving a sequence of electrical flow problems with varying resistances on the edges. Each of these electrical flow problems can be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time.
By representing the graph as a matrix, where each node in the graph is assigned one row and one column of the matrix and the number value where one node represented by a row and another node represented by a column intersect represents the capacity for transferring items between those two nodes. In the branch of mathematics known as linear algebra, a row of a matrix can also be interpreted as a mathematical equation, and the tools of linear algebra enable the simultaneous solution of all the equations embodied by all of a matrix’s rows. By repeatedly modifying the numbers in the matrix and re-solving the equations of the Laplacian system, the researchers effectively evaluate the whole graph at once, which turns out to be more efficient than trying out paths one by one.
If V is the number of vertices in a graph, and E is the number of edges between them, then the execution of the fastest previous max-flow algorithm was proportional to (V + E)^(3/2). The execution of the new algorithm is proportional to (V + E)^(4/3). For a network like the Internet, which has hundreds of billions of nodes, the new algorithm could solve the max-flow problem hundreds of times faster than its predecessor. In addition to the immediate practical use of the algorithm, its breakthrough approach will likely cause a paradigm shift in a number of fields and their approach to related problems.
0 comments:
Post a Comment