The complexity of the matroid-greedoid partition problem
- Creators
- Asodi, Vera
- Umans, Christopher
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
- Eprint ID
- 14043
- DOI
- 10.1016/j.tcs.2008.11.019
- Resolver ID
- CaltechAUTHORS:20090422-111344642
- Center for the Mathematics of Information, Caltech
- CCF-0346991
- NSF
- 2004329
- Binational Science Foundation (USA-Israel)
- Alfred P. Sloan Foundation
- Okawa Foundation
- Created
-
2009-04-23Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field