The shortest augmenting path (Sap) algorithm is one of the most classical approaches to the maximum matching and maximum flow problems, e.g., using it Edmonds and Karp (J. ACM
19
(2), 248–264
1972
) ...have shown the first strongly polynomial time algorithm for the maximum flow problem. Quite astonishingly, although it has been studied for many years already, this approach is far from being fully understood. This is exemplified by the online bipartite matching problem. In this problem a bipartite graph
G
= (
W
⊎
B
,
E
) is being revealed online, i.e., in each round one vertex from
B
with its incident edges arrives. After arrival of this vertex we augment the current matching by using shortest augmenting path. It was conjectured by Chaudhuri et al. (INFOCOM’09) that the total length of all augmenting paths found by Sap is
O
(
n
log
n
)
. However, no better bound than
O
(
n
2
)
is known even for trees. In this paper we prove an
O
(
n
log
2
n
)
upper bound for the total length of augmenting paths for trees.
We present an Õ (m 7/10 U 1/7)-time algorithm for the maximum s-t flow problem (and the minimum s-t cut problem) in directed graphs with m arcs and largest integer capacity U. This matches the ...running time of the Õ (mU)10/7)- time algorithm of Madry 30 in the unit-capacity case, and improves over it, as well as over the Õ (m√n log U)-time algorithm of Lee and Sidford 25, whenever U is moderately large and the graph is sufficiently sparse. By well-known reductions, this also implies similar running time improvements for the maximum-cardinality bipartite b-matching problem. One of the advantages of our algorithm is that it is significantly simpler than the ones presented in 30 and 25. In particular, these algorithms employ a sophisticated interior-point method framework, while our algorithm is cast directly in the classic augmenting path setting that almost all the combinatorial maximum flow algorithms use. At a high level, the presented algorithm takes a primal dual approach in which each iteration uses electrical flows computations both to find an augmenting s-t flow in the current residual graph and to update the dual solution. We show that by maintain certain careful coupling of these primal and dual solutions we are always guaranteed to make significant progress.
Pebbles are placed on some vertices of a directed graph. Is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left on its own? We ...give an O(mn)-time algorithm for solving this problem, which we call the 2-gathering problem, where n is the number of vertices and m is the number of edges of the graph. If such a 2-gathering is not possible, the algorithm finds a solution that minimizes the number of solitary pebbles. The 2-gathering problem forms a nontrivial generalization of the nonbipartite matching problem and it is solved by extending the augmenting paths technique used to solve matching problems.
The subject of this paper is maximum weight matchings of graphs. An edge set M of a given graph G is called a matching if and only if any pair of edges in M share no endvertices. A maximum weight ...matching is a matching whose total weight (total sum of edge-weights) is maximum among those of G. The maximum weight matching problem (MWM for short) is to find a maximum weight matching of a given graph. Polynomial algorithms for finding an optimum solution to MWM have already been proposed: for example, an O(|V|4) time algorithm proposed by J. Edmonds, and an O(|E||V| log|V|) time algorithm proposed by H. N. Gabow. Some applications require obtaining a matching of large total weight (not necessarily a maximum one) in realistic computing time. These existing algorithms, however, spend extremely long computing time as the size of a given graph becomes large, and several fast approximation algorithms for MWM have been proposed. In this paper, we propose six approximation algorithms GRS+, GRS_F+, GRS_R+, GRS_S+, LAM_a+ and LAM_as+. They are enhanced from known approximation ones by adding some post-processings that consist of improved search of weight augmenting paths. Their performance is evaluated through results of computing experiment.
Mesh refinement via bidirected flows Höhring, Rolf H.; Müller-Hannemann, Matthias; Wiehe, Karsten
Journal of the ACM,
05/1997, Letnik:
44, Številka:
3
Journal Article
Recenzirano
We investigate a problem arising in the computer-aided design of cars, planes, ships, trains, and other motor vehicles and machines: refine a mesh of curved polygons, which approximates the surface ...of a workpiece, into quadrilaterals so that the resulting mesh is suitable for a numerical analysis. This mesh refinement problem turns out to be strongly
NP
-hard
In commercial CAD systems, this problem is usually solved using a gree
dy approach. However, these algorithms leave the user a lot of patchwork to do afterwards. We introduce a new global approach, which is based on network flow techniques. Abstracting from all geometric and numerical aspects, we obtain an undirected graph with upper and lower capacities on the edges and some additional node constraints. We reduce this problem to a sequence of bidirected flwo problems (or, equivalently, to
b
-matching problems). For the first time, network flow techniques are applied to a mesh refinement problem.
This approach avoids the local traps of greedy approaches and yields solutions that require significantly less additional patchwork.
A parallel version of the shortest augmenting path algorithm for the assignment problem is described. Although generating the initial dual solution and partial assignment in parallel does not require ...substantive changes in the sequential algorithm, using several augmenting paths in parallel does require a new dual variable recalculation method. The parallel algorithm was tested on a 14-bit processor Butterfly Plus computer, using problems with up to 900 million variables. The speedup obtained increases with problem size. The algorithm also was embedded into a parallel branch and bound procedure for the traveling salesman problem on a directed graph, which was tested on the Butterfly Plus with problems involving up to 30,000 cities. It is concluded that the parallel algorithm seems to perform remarkably well on assignment problems with various cost structures.
Layered Augmenting Path Algorithms Tardos, Eva; Tovey, Craig A; Trick, Michael A
Mathematics of operations research,
05/1986, Letnik:
11, Številka:
2
Journal Article
Recenzirano
Augmenting path algorithms, first introduced by Ford and Fulkerson (Ford, L. R., D. R. Fulkerson. 1962. Flows in Networks . Princeton University Press, Princeton, N.J.), are widely used in ...optimization. Examples include Schönsleben's polymatroid intersection algorithm (Schönsleben, P. 1980. Ganzzahlige polymatroid-intersection-algorithmen. Ph.D. thesis, Eidgenössischen Technischen Hochschule, Zürich.), the maximum polymatroidal network flow algorithm of Lawler and Martel (Lawler, E. L., C. U. Martel. 1982. Computing maximal polymatroidal network flows. Math. Oper. Res. 7 334–347.), Frank's algorithm for the Edmonds–Giles polyhedron (Frank, A. 1984. Finding feasible vectors of Edmonds-Giles polyhedra. J. Combin. Theory Ser. B 36 221-239.) and Cunningham's algorithm for testing membership in matroid polyhedra (Cunningham, H. W. 1984. Testing membership in matroid polyhedra. J. Combin. Theory Ser. B 36 161–188.).
Here we give an order of magnitude improvement for the above algorithms by using an approach analogous to that of Dinits maximum flow algorithm (Dinits, E. A. 1970. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Dokl. 11 1277–1280.).
PDF
