A framework for the greedy algorithm
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.
- A geometric characterization of Coxeter matroids
- Combinatorial geometries and torus strata on homogeneous compact manifolds
- Greedy algorithm and symmetric matroids
- scientific article; zbMATH DE number 4019084 (Why is no real title available?)
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3871387 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- Matroids and the greedy algorithm
- Optimal assignments in an ordered set: An application of matroid theory
- Symplectic matroids
- The greedy algorithm and Coxeter matroids
- A general model for matroids and the greedy algorithm
- The 2-quasi-greedy algorithm for cardinality constrained matroid bases
- Linear objective functions on certain classes of greedoids
- A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids
- Greedy algorithm compatibility and heavy-set structures
- Greedy sets and related problems
- A greedy algorithm for some classes of integer programs.
- The greedy algorithm and Coxeter matroids
- A greedy algorithm for interval greedoids
- Greedy algorithm with gaps
- A disturbed version of the greedy algorithm
- On greedy bases packing in matroids
- Rewarding maps: On greedy optimization of set functions
- A greedoid and a matroid inspired by Bhargava's \(p\)-orderings
- A ranking model for the greedy algorithm and discrete convexity
- A greedy algorithm for maximizing a linear objective function
- On greedy and submodular matrices
- Matroid representation of clique complexes
- Greed is (Sometimes) Not Enough
- scientific article; zbMATH DE number 4191657 (Why is no real title available?)
- Problems on independence systems solvable by the greedy algorithm
- A note on k-limited maximum base
- A class of greedy algorithms and its relation to greedoids
- scientific article; zbMATH DE number 3904604 (Why is no real title available?)
- On ordered languages and the optimization of linear functions by greedy algorithms
- Greedy algorithm and symmetric matroids
- On the Greedy Solution of Ordering Problems
- scientific article; zbMATH DE number 169611 (Why is no real title available?)
- On the greedy algorithm for stochastic optimization problems
- scientific article; zbMATH DE number 194516 (Why is no real title available?)
- An Exact Characterization of Greedy Structures
- Greedy algorithms and poset matroids
- On the generality of the greedy algorithm for solving matroid base problems
- Monge properties, optimal greedy policies, and policy improvement for the dynamic stochastic transportation problem
- Fast greedy for linear matroids
- An order-theoretic framework for the greedy algorithm with applications to the core and Weber set of cooperative games
- The greedy algorithm as a combinatorial principle
- Valuated matroids -- a new look at the greedy algorithm
- Shadows of Newton polytopes
- Matroids And Greedy Algorithms. A Deeper Justification of Using Greedy Approach To Find A Maximal set of a Matroid
- Learning to sample initial solution for solving 0-1 discrete optimization problem by local search
- Weakly greedy algorithm and pair-Delta-matroids
- A backtracking algorithm for solving the nearly equitable strong edge-coloring problem on transportation network
- Valuated matroids: A new look at the greedy algorithm
This page was built for publication: A framework for the greedy algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1613405)
