A simple PTAS for weighted matroid matching on strongly base orderable matroids

DOI10.1016/j.dam.2012.10.019zbMath1288.05036OpenAlexW2106369102MaRDI QIDQ2448875

Jose A. Soto

Publication date: 5 May 2014

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

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

zbMATH Keywords

local searchmatroid parityPTASmatroid matchingstrongly base orderable matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Feedback vertex set reconfiguration in planar graphs ⋮ Weighted matching with pair restrictions ⋮ Robust Randomized Matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Matroid matching
• Complexity of Matroid Property Algorithms
• Random pseudo-polynomial algorithms for exact matroid problems
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees