On the complexity of local search for weighted standard set problems

DOI10.1007/978-3-642-13962-8_15zbMATH Open1286.68226arXiv1004.0871OpenAlexW3104453668MaRDI QIDQ3576199FDOQ3576199

Authors: Dominic Dumrauf, Tim Süß 

Publication date: 29 July 2010

Published in: Programs, Proofs, Processes (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1004.0871

Recommendations

• A note on the complexity of local search problems
• Simple Local Search Problems that are Hard to Solve
• How easy is local search?
• On local search for weighted \(k\)-set packing
• scientific article; zbMATH DE number 18531

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (4)

• On local search for weighted \(k\)-set packing
• Finding 3-swap-optimal independent sets and dominating sets is hard
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• On local search for weighted \(k\)-set packing

This page was built for publication: On the complexity of local search for weighted standard set problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576199)