Constrained k-center and movement to independence

DOI10.1016/J.DAM.2011.01.008MaRDI QIDQ534356zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Minghui Jiang

Publication date 17 May 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.01.008

zbMATH Keywords

linear programmingapproximation algorithmcomputational geometryindependent setclient-server problemfixed parameter tractable algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• An approximation algorithm for \(k\)-center problem on a convex polygon
• \(k\)-center problems with minimum coverage
• Approximation algorithm for the kinetic robust \(k\)-center problem
• Clustering with center constraints

Cites work

• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• Approximation algorithms for spreading points
• Dispersion in unit disks
• Minimizing movement
• Minimizing movement in mobile facility location problems
• Planar Formulae and Their Uses
• Systems of distant representatives
• Universality considerations in VLSI circuits

Cited in

(4)

• The Euclidean \(k\)-supplier problem in \(I R^2\)
• Constrained \(k\)-center problem on a convex polygon
• Dispersion in disks
• Fast solution of single-machine scheduling problem with embedded jobs

This page was built for publication: Constrained \(k\)-center and movement to independence

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