On the complexity of local search for weighted standard set problems

DOI10.1007/978-3-642-13962-8_15MaRDI QIDQ3576199zbMATH OpenOpenAlexFDO

Authors Dominic Dumrauf, Tim Süß

Publication date 29 July 2010

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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.

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

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)