Approximate solution of the \(p\)-median minimization problem

DOI10.1134/S0965542516090074zbMath1362.90324OpenAlexW2527425533MaRDI QIDQ519693

A. A. Navrotskaya, Victor Petrovich Il'ev, Svetlana Il'eva

Publication date: 5 April 2017

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0965542516090074

zbMATH Keywords

combinatorial optimization\(p\)-mediansupermodular set functiongradient algorithmperformance guarantee

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

Optimization of the number and arrangement of circles of two radii for forming a \(k\)-covering of a bounded set

Cites Work

• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• Computational bounds for local search in combinatorial optimization
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Local search heuristic for k-median and facility location problems
• An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximate solution of the \(p\)-median minimization problem