Greedy Oriented Flows

Ulrich Faigle, Walter Kern* (Corresponding Author), Britta Peis

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

39 Downloads (Pure)

Abstract

We investigate the following greedy approach to attack linear programs of type (Formula presented.) where A has entries in (Formula presented.): 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 (Formula presented.), and (Formula presented.), 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 (Formula presented.) 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.

Original languageEnglish
Pages (from-to)1298-1314
Number of pages17
JournalAlgorithmica
Volume80
Issue number4
DOIs
Publication statusPublished - 1 Apr 2018

Keywords

  • UT-Hybrid-D
  • Greedy algorithm
  • Max flow
  • Regular matroid
  • Cycle cancelling

Fingerprint Dive into the research topics of 'Greedy Oriented Flows'. Together they form a unique fingerprint.

Cite this