An approximation algorithm for \(k\)-center problem on a convex polygon

DOI10.1007/s10878-012-9532-5zbMath1322.90075OpenAlexW2054853091MaRDI QIDQ2015790

Hai Du, Yin-Feng Xu

Publication date: 24 June 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9532-5

zbMATH Keywords

convex polygonfacility location\(k\)-center

Mathematics Subject Classification ID

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

Related Items (7)

The polygon burning problem ⋮ The Euclidean \(k\)-supplier problem in \(I R^2\) ⋮ Efficient algorithms for computing one or two discrete centers hitting a set of line segments ⋮ The connected disk covering problem ⋮ Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares ⋮ Constrained k-Center Problem on a Convex Polygon ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

Cites Work

• Base station placement on boundary of a convex polygon
• The 2-Center Problem with Obstacles
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION
• The p-center location problem in an area
• Applications of Parametric Searching in Geometric Optimization
• Unnamed Item
• Unnamed Item

This page was built for publication: An approximation algorithm for \(k\)-center problem on a convex polygon