A general model for matroids and the greedy algorithm
The authors present a general model for matroid independence systems. The proposed model is based on the link between a family of subsets that includes the level set of the linear function to be optimized and a family of feasible solutions. The authors discuss the relationship between the proposed model of matroids and classical matroids. They show that the proposed model extends many of the models for generalized matroid-type greedy algorithms and, in particular, integral polymatroids. The authors introduce the notion of the base chain property and obtain a convenient framework for matroid duality. They discuss matroids that are defined with respect to closure and co-closure systems. The authors provide the construction of a Dilworth embedding and reduce matroids on distributive lattices of closed sets to the classical matroid theory.
- A general class of greedily solvable linear programs
- A greedy algorithm for some classes of integer programs.
- An intersection theorem for supermatroids
- An order-theoretic framework for the greedy algorithm with applications to the core and Weber set of cooperative games
- Dual greedy polyhedra, choice functions, and abstract convex geometries
- scientific article; zbMATH DE number 4027489 (Why is no real title available?)
- scientific article; zbMATH DE number 3777562 (Why is no real title available?)
- scientific article; zbMATH DE number 3272833 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Matroids and the greedy algorithm
- Matroids on convex geometries (cg-matroids)
- Matroids on partially ordered sets
- On ordered languages and the optimization of linear functions by greedy algorithms
- On the core of ordered submodular cost games
- Optimal assignments in an ordered set: An application of matroid theory
- Structural aspects of ordered polymatroids
- Submodular functions and optimization.
- Submodular linear programs on forests
- The greedy algorithm for partially ordered sets
- The theory of convex geometries
- A greedy algorithm for solving ordinary transportation problem with capacity constraints
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- A ranking model for the greedy algorithm and discrete convexity
- Greedy algorithms and poset matroids
- On the generality of the greedy algorithm for solving matroid base problems
- On the rank functions of \(\mathcal{H}\)-matroids
- scientific article; zbMATH DE number 6469169 (Why is no real title available?)
- An order-theoretic framework for the greedy algorithm with applications to the core and Weber set of cooperative games
- Matroids on convex geometries: subclasses, operations, and optimization
- A problem reduction based approach to discrete optimization algorithm design
This page was built for publication: A general model for matroids and the greedy algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1013980)
