scientific article; zbMATH DE number 169611
The paper considers the following classical problem: for a given family J of admissible subsets of a discrete set \(S\), and a given weight function \(w: 2^ s\to R^ +\), find an admissible set of maximum weight. As is well-known, the ``greedy algorithm (choose the heaviest element at each step, provided that the resulting set is still admissible), produces an optimal set iff the underlying structure is a matroid. For ``defective independence systems (that are obtained from matroids by substituting the augmentation axiom with an exchange axiom), the ``greedy algorithm is in general suboptimal. The main result of the paper, however, is that in certain cases such an algorithm provides at least a subset of a maximum weight admissible set. More precisely, an ``exchange index \(q\) is defined as follows: \(q=\max\{\min| Y|: (A\cup x)-Y\in J;\;\forall\;A\in J,\;\forall x\in S-A\}\). Then, the main result of the paper reads as follows: the ``greedy algorithm performs the ``right choice until the element to be inserted into the solution has weight \(w(x)\geq w(X)\), for any \(X\) of cardinality \(q\), whose elements are chosen from the elements of \(S\), that have not been considered for possible insertion in the previous steps. Though not reported in the paper, it can be shown that such results can be somewhat extended to ``defective reduction systems, that are obtained from ``greedoids, by substituting the augmentation axiom with a weaker exchange axiom.
- Some basic exchange properties in combinatorial optimization and their application to constructing the k-best solutions
- Greedy algorithm compatibility and heavy-set structures
- Hereditary systems and greedy-type algorithms.
- The greedy algorithm and Coxeter matroids
- A greedy algorithm for interval greedoids
- Greedy algorithm with gaps
- A disturbed version of the greedy algorithm
- When the greedy algorithm fails
- Matroidal approximations of independence systems
- A generalization of the notion of the rank function of a matroid
- A greedy algorithm for maximizing a linear objective function
- Neighbor systems and the greedy algorithm
- Problems on independence systems solvable by the greedy algorithm
- scientific article; zbMATH DE number 20942 (Why is no real title available?)
- scientific article; zbMATH DE number 2165210 (Why is no real title available?)
- An Exact Characterization of Greedy Structures
- On the generality of the greedy algorithm for solving matroid base problems
- Greedy in Approximation Algorithms
- The greedy algorithm as a combinatorial principle
- Matroids And Greedy Algorithms. A Deeper Justification of Using Greedy Approach To Find A Maximal set of a Matroid
- Weakly greedy algorithm and pair-Delta-matroids
- On performance of greedy algorithms
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038320)
