TY - JOUR
T1 - A constructive proof of Swap Local Search worst-case instances for the Maximum Coverage Problem
AU - Kerkkamp, R.B.O.
AU - Aardal, K.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Locality gap
KW - Maximum Weighted Coverage problem
KW - Swap Local Search
KW - Symmetry
KW - Worst-case performance
UR - http://www.scopus.com/inward/record.url?scp=84961613990&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2016.03.001
DO - 10.1016/j.orl.2016.03.001
M3 - Article
AN - SCOPUS:84961613990
SN - 0167-6377
VL - 44
SP - 329
EP - 335
JO - Operations Research Letters
JF - Operations Research Letters
IS - 3
ER -