Greedoids and Linear Objective Functions

DOI10.1137/0605024MaRDI QIDQ3323971zbMATHOpenAlexFDO

Authors 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)

Recommendations

• Greedoids
• Introduction to Greedoids
• scientific article; zbMATH DE number 3904604
• scientific article; zbMATH DE number 4137538
• scientific article; zbMATH DE number 3871387

Cites work

• scientific article; zbMATH DE number 3742601 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• Algorithmic versus axiomatic definitions of matroids
• Complexity of Matroid Property Algorithms
• Linear objective functions on certain classes of greedoids
• Structural properties of greedoids
• The greedy algorithm for partially ordered sets

Cited in

(25)

• scientific article; zbMATH DE number 4137538 (Why is no real title available?)
• Linear objective functions on certain classes of greedoids
• Advice complexity of adaptive priority algorithms
• Randomized priority algorithms
• Introduction to Greedoids
• Greedy Families for Linear Objective Functions
• scientific article; zbMATH DE number 3871387 (Why is no real title available?)
• Operations on greedoids
• A greedy algorithm for maximizing a linear objective function
• Problems on independence systems solvable by the greedy algorithm
• Greedoids and searches in directed graphs
• New polyhedral and algorithmic results on greedoids
• The application of automated reasoning to formal models of combinatorial optimization
• A framework for the greedy algorithm
• Lexicographically Optimal Base of a Submodular System with respect to a Weight Vector
• Greedy algorithm compatibility and heavy-set structures
• Greedoid polyhedra
• Exchange systems
• Basis graphs of greedoids and two-connectivity
• Polymatroid greedoids
• An algorithmic characterization of antimatroids
• The Greedy Algorithm and the Cohen-Macaulay Property of Rings, Graphs and Toric Projective Curves
• Branchings in rooted graphs and the diameter of greedoids
• A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids
• Sufficient conditions for the optimality of the greedy algorithm in greedoids

This page was built for publication: Greedoids and Linear Objective Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3323971)