On greedy and submodular matrices

DOI10.1007/978-3-642-19754-3_13zbMATH Open1325.90062arXiv1206.5167OpenAlexW2132508746MaRDI QIDQ2999339FDOQ2999339

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)

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.

Full work available at URL: https://arxiv.org/abs/1206.5167

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

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)

Cited In (6)

• On the submodular matrix representation of a digraph.
• Greedy oriented flows
• On supmodular matrices
• On greedy bases packing in matroids
• 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)