Portal del Investigador
A simple PTAS for weighted matroid matching on strongly base orderable matroids
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. (C) 2012 Elsevier B.V. All rights reserved.
Más información
| Título según WOS: | A simple PTAS for weighted matroid matching on strongly base orderable matroids |
| Título de la Revista: | DISCRETE APPLIED MATHEMATICS |
| Volumen: | 164 |
| Editorial: | ELSEVIER SCIENCE BV |
| Fecha de publicación: | 2014 |
| Página de inicio: | 406 |
| Página final: | 412 |
| Idioma: | English |
| URL: | http://linkinghub.elsevier.com/retrieve/pii/S0166218X1200399X |
| DOI: |
10.1016/j.dam.2012.10.019 |
| Notas: | ISI |