On greedy and submodular matrices

DOI10.1007/978-3-642-19754-3_13MaRDI QIDQ2999339zbMATH OpenOpenAlexFDO

Authors U. Faigle, Walter Kern, Britta Peis

Publication date 12 May 2011

Published in Theory and Practice of Algorithms in (Computer) Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.5167, https://research.utwente.nl/en/publications/on-greedy-and-submodular-matrices(a61cf8c1-8fa9-4100-aeb0-21ea8abe0dba).html

zbMATH Keywords

linear programmingsubmodularitymax flow

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Linear programming (90C05) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Flows in graphs (05C21)

Abstract: The max-flow and max-coflow problem on directed graphs is studied in the common generalization to regular spaces, i.e., to kernels or row spaces of totally unimodular matrices. Exhibiting a submodular structure of the family of paths within this model we generalize the Edmonds-Karp variant of the classical Ford-Fulkerson method and show that the number of augmentations is quadratically bounded if augmentations are chosen along shortest possible augmenting paths.

Recommendations

• A Characterization of Nonnegative Box-Greedy Matrices
• A framework for the greedy algorithm
• A general class of greedily solvable linear programs
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• scientific article; zbMATH DE number 4191657

Cited in

(6)

• On the submodular matrix representation of a digraph.
• Greedy oriented flows
• On greedy bases packing in matroids
• On supmodular matrices
• A refined analysis of submodular greedy
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond

This page was built for publication: On greedy and submodular matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2999339)