Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 1, 2009 | public
Journal Article

The complexity of the matroid-greedoid partition problem

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.

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.

Additional details

Created:
August 21, 2023
Modified:
October 18, 2023