Well-layered maps---a class of greedily optimizable set functions
From MaRDI portal
The paper contains a characterization of the well-layered maps by an appropriate quantified version of the greedoid exchange condition. The authors hope that this theorem can be applied to a problem discussed by Murota, viz. the problem of finding a \(k\)-subdeterminant of highest degree in an \(n \times n\)-matrix, whose entries are rational polynomials in one or several variables.
Recommendations
- Well-layered maps and the maximum-degree k k-subdeterminant of a matrix of rational functions
- On the problem of maximizing a modular function in the geometric lattice
- scientific article; zbMATH DE number 3904604
- Rewarding maps: On greedy optimization of set functions
- Greedy Families for Linear Objective Functions
Cites work
- 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
- Greedoids
- Valuated matroids: A new look at the greedy algorithm
Cited in
(11)- Discrete convex analysis
- Monotone linkage clustering and quasi-concave set functions
- A greedy algorithm for some classes of integer programs.
- Layered clusters of tightness set functions
- Gross substitutability: an algorithmic survey
- Simpler exchange axioms for M-concave functions on generalized polymatroids
- Well-layered maps and the maximum-degree k k-subdeterminant of a matrix of rational functions
- Two algorithms for valuated \(\Delta\)-matroids
- Computing Walrasian equilibria: fast algorithms and structural properties
- Convexity and Steinitz's exchange property
- On the construction of substitutes
This page was built for publication: Well-layered maps---a class of greedily optimizable set functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1904519)
