A constructive proof of swap local search worst-case instances for the maximum coverage problem

DOI10.1016/j.orl.2016.03.001zbMath1408.90163OpenAlexW2295783295MaRDI QIDQ1790189

R. B. O. Kerkkamp, Karen Aardal

Publication date: 2 October 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/25094

zbMATH Keywords

symmetryworst-case performancelocality gapmaximum weighted coverage problemswap local search

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (2)

Unnamed Item ⋮ Orientational variable-length strip covering problem: a branch-and-price-based algorithm

Cites Work

• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Unnamed Item
• Unnamed Item

This page was built for publication: A constructive proof of swap local search worst-case instances for the maximum coverage problem