Full Paper: Search Google Scholar

We consider submodular optimization problems, and provide a general way of translating oracle inapproximability results arising from the symmetry gap technique to computational complexity inapproximability results, where the submodular function is given explicitly (under the assumption that NP ≠ RP). Applications of our technique include an optimal computational hardness of (1/2 + ε)-approximation for maximizing a symmetric nonnegative submodular function, an optimal hardness of (1-(1-1/k)k + ε)-approximation for welfare maximization in combinatorial auctions with k submodular bidders (for constant k), super-constant hardness for maximizing a nonnegative submodular function over matroid bases, and tighter bounds for maximizing a monotone submodular function subject to a cardinality constraint.

 

 

 

Discussion

Post anonymously: (You can change the anonymity of a comment at any time.)

You must be logged in to comment. Log in

No comments yet.