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

facility locationconvex polygon\(k\)-center

Mathematics Subject Classification ID

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

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

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

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)