  


The Complexity of Maximum MatroidGreedoid Intersection and Weighted Greedoid Maximization
Taneli Mielikäinen (Taneli.Mielikaineniki.fi) Abstract: The maximum intersection problem for a matroid and a greedoid, given by polynomialtime 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 matroidmatroid 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, FixedParameter Intractability Category 1: Combinatorial Optimization Citation: unpublished: Report C20042, Department of Computer Science, University of Helsinki, Finland Download: [PDF] Entry Submitted: 02/11/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  