A constructive proof of Swap Local Search worst-case instances for the Maximum Coverage Problem

R.B.O. Kerkkamp*, K. Aardal

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

Abstract

We consider the Maximum Weighted Coverage problem (MCP). We can relate the MCP to optimisation problems using submodular functions. Performance guarantees of the Swap Local Search algorithm are known for these problems, but can be improved for the MCP. Our main contribution is a constructive proof of tight performance guarantees for Swap Local Search applied to the MCP, which provides insight into the structure of worst-case MCP instances, and has the potential to be applicable to other optimisation problems.

Original languageEnglish
Pages (from-to)329-335
Number of pages7
JournalOperations Research Letters
Volume44
Issue number3
DOIs
Publication statusPublished - 2016

Keywords

  • Locality gap
  • Maximum Weighted Coverage problem
  • Swap Local Search
  • Symmetry
  • Worst-case performance

Fingerprint

Dive into the research topics of 'A constructive proof of Swap Local Search worst-case instances for the Maximum Coverage Problem'. Together they form a unique fingerprint.

Cite this