The Complexity of the Matroid-Greedoid Partition Problem (2008)

by Vera Asodi. Christopher Umans.

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 [5] can be used to obtain codes with these properties. We also show that the parameterized matroid-greedoid partition problem is fixed-parameter tractable. [via]

http://www.cs.caltech.edu/~umans/papers/AU08....