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

DOI10.1007/S10878-012-9532-5MaRDI QIDQ2015790zbMATH OpenOpenAlexFDO

Authors Hai Du, Yinfeng 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

\(k\)-centerconvex polygonfacility location

Mathematics Subject Classification ID

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

Recommendations

• Constrained k-center problem on a convex polygon
• An incremental version of the \(k\)-center problem on boundary of a convex polygon
• An approximation algorithm for the continuous k-medians problem in a convex polygon
• The connected disk covering problem
• Computing the line-constrained k-center in the plane for small k

Cites work

• Applications of Parametric Searching in Geometric Optimization
• Base station placement on boundary of a convex polygon
• scientific article; zbMATH DE number 1696646 (Why is no real title available?)
• Some constrained minimax and maximin location problems
• The 2-center problem with obstacles
• The p-center location problem in an area
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION

Cited in

(26)

• An algorithm for finding the Chebyshev center of a convex polyhedron
• The mixed center location problem
• The connected disk covering problem
• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• On the k-center problem with many centers
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• The polygon burning problem
• Efficient algorithms for computing one or two discrete centers hitting a set of line segments
• The Euclidean \(k\)-supplier problem in \(I R^2\)
• Geometric partitioning and robust ad-hoc network design
• Computing the line-constrained k-center in the plane for small k
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• An approximation algorithm for the continuous k-medians problem in a convex polygon
• THE ALIGNED K-CENTER PROBLEM
• scientific article; zbMATH DE number 2089224 (Why is no real title available?)
• A Best Possible Heuristic for the k-Center Problem
• A Polynomial Time Approximation Scheme for the Closest Shared Center Problem
• Constrained \(k\)-center and movement to independence
• New Algorithms for k-Center and Extensions
• Constrained k-center problem on a convex polygon
• Clustering geometrically-modeled points in the aggregated uncertainty model
• A faster algorithm for the constrained minimum covering circle problem to expedite solving p‐center problems in an irregularly shaped area with holes
• On solving the planar k-centrum problem with Euclidean distances
• Approximation algorithms for a \(k\)-line center
• New algorithms for \(k\)-center and extensions
• An incremental version of the \(k\)-center problem on boundary of a convex polygon

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2015790)