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

DOI10.1007/S10878-012-9532-5zbMATH Open1322.90075OpenAlexW2054853091MaRDI QIDQ2015790FDOQ2015790

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

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\)

zbMATH Keywords

facility locationconvex polygon\(k\)-center

Mathematics Subject Classification ID

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

Cites Work

• The p-center location problem in an area
• Applications of Parametric Searching in Geometric Optimization
• Title not available (Why is that?)
• Base station placement on boundary of a convex polygon
• Some constrained minimax and maximin location problems
• The 2-center problem with obstacles
• 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
• New Algorithms for k-Center and Extensions
• New algorithms for \(k\)-center and extensions
• Geometric partitioning and robust ad-hoc network design
• 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
• 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
• Approximation algorithms for a \(k\)-line center
• An incremental version of the \(k\)-center problem on boundary of a convex polygon
• Clustering geometrically-modeled points in the aggregated uncertainty model
• 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
• 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
• A Best Possible Heuristic for the k-Center Problem
• Title not available (Why is that?)
• The connected disk covering problem
• 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)