کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436210 | 689977 | 2009 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 410, Issues 8–10, 1 March 2009, Pages 859-866