Paper Info
Title
The complexity of the matroid–greedoid partition problem
Abstract
We show that the maximum matroid-greedoid partition problem isNP-hard to approximate to within 1/2+ε for anyε0, which matches the trivial factor 1/2 approximationalgorithm. The main tool in our hardness of approximation result isan extractor code with polynomial rate, alphabet size andlist size, together with an efficient algorithm for list-decoding.We show that the recent extractor construction of Guruswami, Umansand Vadhan [V. Guruswami, C. Umans, S.P. Vadhan, Unbalancedexpanders 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 theseproperties. We also show that the parameterized matroid-greedoidpartition problem is fixed-parameter tractable.
Year
DOI
Venue
2009
10.1016/j.tcs.2008.11.019
Theor. Comput. Sci.
Keywords
DocType
Volume
Extractor codes,IEEE Conference,Umansand Vadhan,randomness extractor,Greedoid,Parvaresh-Vardy code,approximation result isan extractor,V. Guruswami,Matroid,Matroid partition problem,alphabet size andlist size,parameterized matroid-greedoidpartition problem,Fixed-parameter complexity,IEEE Computer Society,maximum matroid-greedoid partition problem
Journal
410
Issue
ISSN
Citations 
8-10
Theoretical Computer Science
2
PageRank 
References 
Authors
0.37
11
2
Name
Order
Citations
PageRank
Vera Asodi1323.47
Christopher Umans287955.36