Problems on independence systems solvable by the greedy algorithm

DOI10.1515/DMA.2009.034zbMATH Open1237.05037MaRDI QIDQ3225892FDOQ3225892

Authors: Victor Petrovich Il'ev 

Publication date: 23 March 2012

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

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

zbMATH Keywords

Rado-Edmonds theoremmaximisation problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Representation of fragmentary structures by oriented graphs
• On the problem of maximizing a modular function in the geometric lattice
• It is hard to know when greedy is good for finding independent sets
• Greedy-type resistance of combinatorial problems
• A generalization of the notion of the rank function of a matroid
• Title not available (Why is that?)
• Objective functions with redundant domains
• A greedy algorithm for maximizing a linear objective function
• Title not available (Why is that?)

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)