The complexity of the matroid-greedoid partition problem

被引：3

作者：

Asodi, Vera ^{[1
]}

Umans, Christopher ^{[1
]}

机构：

[1] CALTECH, Pasadena, CA 91125 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 8-10期

关键词：

Matroid; Greedoid; Matroid partition problem; Extractor codes; Fixed-parameter complexity; EXTRACTORS;

D O I：

10.1016/j.tcs.2008.11.019

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that the maximum matroid-greedoid partition problem is NP-hard to approximate to within 1/2 + epsilon for any epsilon > 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. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：859 / 866

页数：8

共 15 条

[1] SIMPLE CONSTRUCTIONS OF ALMOST K-WISE INDEPENDENT RANDOM-VARIABLES
ALON, N
GOLDREICH, O
HASTAD, J
PERALTA, R
[J]. RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (03) : 289 - 304
[2] [Anonymous], S THEOR COMP STOC
[3] [Anonymous], 1991, Greedoids
[4] Downey R.G., 1999, MG COMP SCI, DOI 10.1007/978-1-4612-0515-9
[5] FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .1. BASIC RESULTS
DOWNEY, RG
FELLOWS, MR
[J]. SIAM JOURNAL ON COMPUTING, 1995, 24 (04) : 873 - 921
[6] MINIMUM PARTITION OF A MATROID INTO INDEPENDENT SUBSETS
EDMONDS, J
[J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 67 - +
[7] Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
Guruswami, Venkatesan
Umans, Christopher
Vadhan, Salil
[J]. TWENTY-SECOND ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2007, : 96 - +
[8] Korte B., 1981, P 1981 INT FCT C FUN, P205
[9] The complexity of maximum matroid-greedoid intersection and weighted greedoid maximization
Mielikäinen, T
Ukkonen, E
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (04) : 684 - 691
[10] Simple extractors for all min-entropies and a new pseudorandom generator
Shaltiel, R
Umans, C
[J]. JOURNAL OF THE ACM, 2005, 52 (02) : 172 - 216

← 1 2 →