The greedy algorithm and Coxeter matroids
type: Item
instance of: scholarly article
title: The greedy algorithm and Coxeter matroids
zbMATH Open document ID: 0979.05029
DOI: 10.1023/A:1008780132748
published in: Journal of Algebraic Combinatorics
publication date: 2002-02-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1491053
zbMATH Keywords: greedy algorithm
zbMATH Keywords: Coxeter matroid
zbMATH Keywords: Bruhat order
zbMATH Keywords: Gale order
author: Andrew Vince
reviewed by: Vincent Moulton
MaRDI profile type: Publication
cites work: Symplectic matroids
cites work: Boundaries of Coxeter matroids
cites work: The lattice of flats and its underlying flag matroid polytope
cites work: An adjacency criterion for Coxeter matroids
cites work: Greedy algorithm and symmetric matroids
cites work: Some characterizations of Coxeter groups
cites work: Combinatorial geometries, convex polyhedra, and Schubert cells
cites work: Q3030842
cites work: Combinatorial geometries and torus strata on homogeneous compact manifolds
cites work: Q3942064
cites work: Greedoids
cites work: Bruhat lattices, plane partition generating functions, and minuscule representations
cites work: A geometric characterization of Coxeter matroids
cites work: Q3961400
description: scientific article; zbMATH DE number 1491053