A framework for the greedy algorithm
type: Item
instance of: scholarly article
title: A framework for the greedy algorithm
zbMATH Open document ID: 1007.05038
DOI: 10.1016/S0166-218X(01)00362-6
author: R. Smith
published in: Discrete Applied Mathematics
publication date: 2002-08-29T00:00:00Z
review text: Matroids are characterized by the fact that the greedy algorithm finds bases of largest weight. There are, however, optimization problems for which the greedy algorithm solves the optimization problem for many, but not all, linear weight functions and for such situations a theory is developed to efficiently identify instances on which the greedy algorithm works correctly. For a finite set together with a set of partial orderings on its elements, the concepts of greedy set and admissible function are defined, meaning that on a greedy set the greedy algorithm correctly solves the associated optimization problem for all admissible functions. A geometric condition sufficient for a set to be greedy is given in terms of a polytope and roots that generalize Lie algebra root systems. The main ideas are illustrated by many nice examples.
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 20F55
zbMATH DE Number: 1792346
zbMATH Keywords: greedy algorithm
zbMATH Keywords: matroid
zbMATH Keywords: Coxeter matroid
reviewed by: Herman J. Servatius
MaRDI profile type: Publication
cites work: Greedy algorithm and symmetric matroids
cites work: Symplectic matroids
cites work: Matroids and the greedy algorithm
cites work: Optimal assignments in an ordered set: An application of matroid theory
cites work: Q3030842
cites work: Combinatorial geometries and torus strata on homogeneous compact manifolds
cites work: Q3338268
cites work: Q3048571
cites work: Q4739657
cites work: A geometric characterization of Coxeter matroids
cites work: The greedy algorithm and Coxeter matroids
full work available at URL: s0166-218x(01)00362-6
OpenAlex ID: W2161029789
description: scientific article; zbMATH DE number 1792346