The greedy algorithm and Coxeter matroids
Given a pair \(M= (X,{\mathcal I})\) consisting of a finite set \(X\) and a non-empty collection \({\mathcal I}\) of subsets of \(X\) together with a function \(\phi:X \to {\mathbb R}\), a natural combinatorial optimization problem is to find a set in \(\mathcal I\) that has greatest total weight. In case \(\phi\) is positive, it is well known this can be solved using a greedy algorithm in case \(M\) is a matroid. In this paper it is shown that a greedy algorithm also provides a solution to an optimization problem that can be naturally associated to Coxeter matroids. This is shown to generalize the above result for matroids, which are special examples of Coxeter matroids. The proof of the main result has an important consequence for Coxeter matroids in that it provides the notions of bases and independent sets for these objects. As an application of the main result a greedy algorithm is given that is shown to solve the \(L\)-assignment problem in case \(L\) is a Coxeter matroid.
- A geometric characterization of Coxeter matroids
- An adjacency criterion for Coxeter matroids
- Boundaries of Coxeter matroids
- Bruhat lattices, plane partition generating functions, and minuscule representations
- Combinatorial geometries and torus strata on homogeneous compact manifolds
- Combinatorial geometries, convex polyhedra, and Schubert cells
- Greedoids
- Greedy algorithm and symmetric matroids
- scientific article; zbMATH DE number 4019084 (Why is no real title available?)
- scientific article; zbMATH DE number 3759173 (Why is no real title available?)
- scientific article; zbMATH DE number 3781925 (Why is no real title available?)
- Some characterizations of Coxeter groups
- Symplectic matroids
- The lattice of flats and its underlying flag matroid polytope
This page was built for publication: The greedy algorithm and Coxeter matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575099)
