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

DOI10.1016/J.DAM.2014.08.034zbMATH Open1320.05020OpenAlexW2086484764MaRDI QIDQ496445FDOQ496445

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

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

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)

Cites Work

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

Cited In (5)

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

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)