Greedoids and Linear Objective Functions

DOI10.1137/0605024zbMath0538.05027OpenAlexW2130640756MaRDI QIDQ3323971

Bernhard Korte, László Lovász

Publication date: 1984

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0605024

zbMATH Keywords

greedy algorithmoptimal basisgreedoid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Algorithms in computer science (68W99)

Related Items

Greedy Families for Linear Objective Functions, Greedoid polyhedra, A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids, An algorithmic characterization of antimatroids, Sufficient conditions for the optimality of the greedy algorithm in greedoids, Branchings in rooted graphs and the diameter of greedoids, Lexicographically Optimal Base of a Submodular System with respect to a Weight Vector, Problems on independence systems solvable by the greedy algorithm, Advice complexity of adaptive priority algorithms, The Greedy Algorithm and the Cohen-Macaulay Property of Rings, Graphs and Toric Projective Curves, New polyhedral and algorithmic results on greedoids, Greedoids and searches in directed graphs, Greedy algorithm compatibility and heavy-set structures, Randomized priority algorithms, Polymatroid greedoids, Exchange systems, The application of automated reasoning to formal models of combinatorial optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Structural properties of greedoids
• Linear objective functions on certain classes of greedoids
• The greedy algorithm for partially ordered sets
• Algorithmic versus axiomatic definitions of matroids
• Complexity of Matroid Property Algorithms