Universität zu Köln

Faigle, Ulrich, Kern, Walter and Peis, Britta (2018). Greedy Oriented Flows. Algorithmica, 80 (4). S. 1298 - 1315. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

Abstract

We investigate the following greedy approach to attack linear programs of type where A has entries in : The greedy algorithm starts with a feasible solution x and, iteratively, chooses an improving variable and raises it until some constraint becomes tight. In the special case, where A is the edge-path incidence matrix of some digraph , and , this greedy algorithm corresponds to the Ford-Fulkerson algorithm to solve the max ( s , t )-flow problem in G w.r.t. edge-capacities u. It is well-known that the Ford-Fulkerson algorithm always terminates with an optimal flow, and that the number of augmentations strongly depends on the choice of paths in each iteration. The Edmonds-Karp rule that prefers paths with fewer arcs leads to a running time of at most augmentations. The paper investigates general types of matrices A and preference rules on the variables that make the greedy algorithm efficient. In this paper, we identify conditions that guarantee for the greedy algorithm not to cycle, and/or optimality of the greedy algorithm, and/or to yield a quadratic (in the number of rows) number of augmentations. We illustrate our approach with flow and circulation problems on regular oriented matroids.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Faigle, Ulrich UNSPECIFIED UNSPECIFIED UNSPECIFIED Kern, Walter UNSPECIFIED UNSPECIFIED UNSPECIFIED Peis, Britta UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-192232
DOI:	10.1007/s00453-017-0306-4
Journal or Publication Title:	Algorithmica
Volume:	80
Number:	4
Page Range:	S. 1298 - 1315
Date:	2018
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language OPTIMIZATION; MATRICES Multiple languages Computer Science, Software Engineering; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/19223