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 http://resolver.caltech.edu/CaltechAUTHORS:20090422-111344642
- Published Version
Restricted to Repository administrators only
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20090422-111344642
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.
|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.|
|Subject Keywords:||Matroid; Greedoid; Matroid partition problem; Extractor codes; Fixed-parameter complexity|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Jason Perez|
|Deposited On:||23 Apr 2009 21:34|
|Last Modified:||26 Dec 2012 10:58|
Repository Staff Only: item control page