On the Complexity of Local Search for Weighted Standard Set Problems

Details On the Complexity of Local Search for Weighted Standard Set Problems On the Complexity of Local Search for Weighted Standard Set Problems

2010-04-06

arxiv.org/abs/1004.0871v1

Computer Science

Computational Complexity

Scientific paper

In this paper, we study the complexity of computing locally optimal solutions for weighted versions of standard set problems such as SetCover, SetPacking, and many more. For our investigation, we use the framework of PLS, as defined in Johnson et al., [JPY88]. We show that for most of these problems, computing a locally optimal solution is already PLS-complete for a simple neighborhood of size one. For the local search versions of weighted SetPacking and SetCover, we derive tight bounds for a simple neighborhood of size two. To the best of our knowledge, these are one of the very few PLS results about local search for weighted standard set problems.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Local Search for Weighted Standard Set Problems 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 On the Complexity of Local Search for Weighted Standard Set Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Local Search for Weighted Standard Set Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57639