Improved Inapproximability For Submodular Maximization

Details Improved Inapproximability For Submodular Maximization Improved Inapproximability For Submodular Maximization

2010-04-21

arxiv.org/abs/1004.3777v1

Computer Science

Computational Complexity

Scientific paper

We show that it is Unique Games-hard to approximate the maximum of a submodular function to within a factor 0.695, and that it is Unique Games-hard to approximate the maximum of a symmetric submodular function to within a factor 0.739. These results slightly improve previous results by Feige, Mirrokni and Vondr\'ak (FOCS 2007) who showed that these problems are NP-hard to approximate to within $3/4 + \epsilon \approx 0.750$ and $5/6 + \epsilon \approx 0.833$, respectively.

Affiliated with

Also associated with

No associations

Rating

Improved Inapproximability For Submodular Maximization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Inapproximability For Submodular Maximization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Inapproximability For Submodular Maximization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-327634