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

DOI10.1016/j.dam.2014.08.034zbMath1320.05020OpenAlexW2086484764MaRDI QIDQ496445

Lara Turner, Horst W. Hamacher, Matthias Ehrgott

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 optimizationgreedy algorithmmatroidsshortest pathsminorstransversal matroidsbipartite matchingsuniform matroidsuniversal objective function

Mathematics Subject Classification ID

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

Cites Work

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