CaltechAUTHORS
  A Caltech Library Service

The complexity of the matroid-greedoid partition problem

Asodi, Vera and Umans, Christopher (2009) The complexity of the matroid-greedoid partition problem. Theoretical Computer Science, 410 (8-10). pp. 859-866. ISSN 0304-3975. https://resolver.caltech.edu/CaltechAUTHORS:20090422-111344642

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20090422-111344642

Abstract

We show that the maximum matroid–greedoid partition problem is NP-hard to approximate to within 1/2+ε for any ε>0, which matches the trivial factor 1/2 approximation algorithm. The main tool in our hardness of approximation result is an extractor code with polynomial rate, alphabet size and list size, together with an efficient algorithm for list-decoding. We show that the recent extractor construction of Guruswami, Umans and Vadhan [V. Guruswami, C. Umans, S.P. Vadhan, Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, in: IEEE Conference on Computational Complexity, IEEE Computer Society, 2007, pp. 96–108] can be used to obtain a code with these properties. We also show that the parameterized matroid–greedoid partition problem is fixed-parameter tractable.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/j.tcs.2008.11.019DOIArticle
Additional Information:© 2008 Elsevier B.V. Received 30 July 2008; revised 17 November 2008; accepted 24 November 2008. Communicated by J. Díaz. Available online 6 December 2008. The first author was supported by a CMI postdoctoral fellowship. The second author was supported by NSF CCF-0346991, BSF 2004329, a Sloan Research Fellowship, and an Okawa Foundation research grant.
Funders:
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
NSFCCF-0346991
Binational Science Foundation (USA-Israel)2004329
Alfred P. Sloan FoundationUNSPECIFIED
Okawa FoundationUNSPECIFIED
Subject Keywords:Matroid; Greedoid; Matroid partition problem; Extractor codes; Fixed-parameter complexity
Issue or Number:8-10
Record Number:CaltechAUTHORS:20090422-111344642
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20090422-111344642
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14043
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:23 Apr 2009 21:34
Last Modified:03 Oct 2019 00:46

Repository Staff Only: item control page