Optimization Online


The Complexity of Maximum Matroid-Greedoid Intersection and Weighted Greedoid Maximization

Taneli Mielikäinen (Taneli.Mielikainen***at***iki.fi)
Esko Ukkonen (Esko.Ukkonen***at***cs.Helsinki.FI)

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 $W[P]$-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 $2^{n^{O(1)}}$ where $n$ is the size of the domain of the greedoid.

Keywords: $NP$-Hardness, Inapproximability, Fixed-Parameter Intractability

Category 1: Combinatorial Optimization

Citation: unpublished: Report C-2004-2, Department of Computer Science, University of Helsinki, Finland

Download: [PDF]

Entry Submitted: 02/11/2004
Entry Accepted: 02/11/2004
Entry Last Modified: 02/11/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society