Complexity of local search for the \(p\)-median problem

DOI10.1016/j.ejor.2006.12.063zbMath1157.90016OpenAlexW2067606835MaRDI QIDQ932191

Ekaterina Alekseeva, Yury A. Kochetov, Aleksandr V. Plyasunov

Publication date: 10 July 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2006.12.063

zbMATH Keywords

local searchKarush-Kuhn-Tucker conditionspseudo-Boolean functionspivoting rulesPLS-completeness0-1 local saddle points

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)

Related Items (7)

Graph pricing with limited supply ⋮ Discrete facility location in machine learning ⋮ Threshold robustness in discrete facility location problems: a bi-objective approach ⋮ Berge-acyclic multilinear 0-1 optimization problems ⋮ Memetic algorithms: The polynomial local search complexity theory perspective ⋮ A Bilevel Competitive Location and Pricing Model with Nonuniform Split of Demand ⋮ The Branch and Cut Method for the Clique Partitioning Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(p\)-median problem: a survey of metaheuristic approaches
• On local search for the generalized graph coloring problem
• Simple Local Search Problems that are Hard to Solve
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• An Efficient Heuristic Procedure for Partitioning Graphs
• Local Search Heuristics for k-Median and Facility Location Problems
• Approximate Local Search in Combinatorial Optimization

This page was built for publication: Complexity of local search for the \(p\)-median problem