The complexity of maximum matroid-greedoid intersection and weighted greedoid maximization |
| |
Authors: | Taneli Mielikäinen |
| |
Institution: | Department of Computer Science, P.O. Box 68, FIN-00014 University of Helsinki, Finland |
| |
Abstract: | The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown NP-hard by expressing the satisfiability of boolean formulas in 3-conjunctive normal form as such an intersection. The corresponding approximation problems are shown NP-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown WP]-hard. The results are in contrast with the maximum matroid-matroid intersection which is solvable in polynomial time by an old result of Edmonds. We also prove that it is NP-hard to approximate the weighted greedoid maximization within 2nO(1) where n is the size of the domain of the greedoid. |
| |
Keywords: | Combinatorial optimization NP-hardness Inapproximability Fixed-parameter intractability |
本文献已被 ScienceDirect 等数据库收录! |
|