Article ID Journal Published Year Pages File Type
419019 Discrete Applied Mathematics 2014 7 Pages PDF
Abstract

We devise a polynomial time approximation scheme (PTAS) for the weighted matroid matching problem on strongly base orderable matroids. We also show that even the unweighted version of this problem is NP-complete and outside Oracle-coNP.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A simple PTAS for weighted matroid matching on strongly base orderable matroids
Authors
,