Problems on independence systems solvable by the greedy algorithm

DOI10.1515/DMA.2009.034MaRDI QIDQ3225892zbMATHFDO

Authors Victor Petrovich Il'ev

Publication date 23 March 2012

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

zbMATH Keywords

Rado-Edmonds theoremmaximisation problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3904604
• A greedy algorithm for maximizing a linear objective function
• A framework for the greedy algorithm
• scientific article; zbMATH DE number 169611
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem

Cites work

• A greedy algorithm for maximizing a linear objective function
• An Exact Characterization of Greedy Structures
• Greedoids and Linear Objective Functions
• Linear objective functions on certain classes of greedoids
• Matroids and the greedy algorithm
• Note on Independence Functions

Cited in

(9)

• On the problem of maximizing a modular function in the geometric lattice
• A generalization of the notion of the rank function of a matroid
• It is hard to know when greedy is good for finding independent sets
• Representation of fragmentary structures by oriented graphs
• A greedy algorithm for maximizing a linear objective function
• Objective functions with redundant domains
• Greedy-type resistance of combinatorial problems
• scientific article; zbMATH DE number 4149905 (Why is no real title available?)
• scientific article; zbMATH DE number 3904604 (Why is no real title available?)

This page was built for publication: Problems on independence systems solvable by the greedy algorithm

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