Well-layered maps---a class of greedily optimizable set functions

DOI10.1016/0893-9659(95)00070-7zbMath0853.05025OpenAlexW1986638647MaRDI QIDQ1904519

Werner F. Terhalle, Andreas W. M. Dress

Publication date: 21 October 1996

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0893-9659(95)00070-7

zbMATH Keywords

matroidsgreedy algorithmsset functionswell-layered mapsgreedoid exchange condition

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (11)

Convexity and Steinitz's exchange property ⋮ Well-layered maps and the maximum-degree \(k \times k\)-subdeterminant of a matrix of rational functions ⋮ Monotone linkage clustering and quasi-concave set functions ⋮ Two algorithms for valuated \(\Delta\)-matroids ⋮ Gross substitutability: an algorithmic survey ⋮ On the Construction of Substitutes ⋮ A greedy algorithm for some classes of integer programs. ⋮ Simpler exchange axioms for M-concave functions on generalized polymatroids ⋮ Computing Walrasian equilibria: fast algorithms and structural properties ⋮ Discrete convex analysis ⋮ Layered clusters of tightness set functions

Cites Work

• Greedoids
• Valuated matroids: A new look at the greedy algorithm
• A greedy-algorithm characterization of valuated \(\Delta\)-matroids
• Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form
• Finding optimal minors of valuated bimatroids

This page was built for publication: Well-layered maps---a class of greedily optimizable set functions