On the generality of the greedy algorithm for solving matroid base problems

DOI10.1016/J.DAM.2014.08.034MaRDI QIDQ496445zbMATH OpenOpenAlexFDO

Authors Lara Turner, Matthias Ehrgott, Horst W. Hamacher

Publication date 21 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2014.08.034

zbMATH Keywords

combinatorial optimizationshortest pathsgreedy algorithmtransversal matroidsmatroidsminorsbipartite matchingsuniform matroidsuniversal objective function

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Recommendations

• A framework for the greedy algorithm
• A general model for matroids and the greedy algorithm
• A greedy algorithm for maximizing a linear objective function
• scientific article; zbMATH DE number 169611
• An Exact Characterization of Greedy Structures

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Algebraic flows in regular matroids
• Balanced optimization problems
• Combinatorial optimization. Networks and matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient algorithms for a family of matroid intersection problems
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Lattice path matroids: structural properties
• Linear and combinatorial optimization in ordered algebraic structures
• Location theory. A unified approach
• Minimal cost flows in regular matroids
• Minimum deviation and balanced optimization: A unified approach
• Minimum deviation problems
• On \(k\)-Max-optimization
• On \(k\)-sum optimization
• On combined minmax-minsum optimization
• On discrete optimization with ordering
• On ordered weighted averaging aggregation operators in multicriteria decisionmaking
• On universal shortest paths
• Ordered weighted average combinatorial optimization: formulations and their properties
• Solving combinatorial problems with combined min-max-min-sum objective and applications
• The algebraic Monge property and path problems
• Two algorithms for weighted matroid intersection
• Variants of shortest path problems
• k-sum optimization problems

Cited in

(5)

• A note on \(k\)-limited maximum base
• Fast greedy for linear matroids
• Greedy algorithm and symmetric matroids
• Mechanisms for Hiring a Matroid Base without Money
• Matroids And Greedy Algorithms. A Deeper Justification of Using Greedy Approach To Find A Maximal set of a Matroid

This page was built for publication: On the generality of the greedy algorithm for solving matroid base problems

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