New Algorithms for k-Center and Extensions

DOI10.1007/978-3-540-85097-7_7zbMath1168.68590OpenAlexW1559325037MaRDI QIDQ5505644

René Brandenberg, Lucia Roth

Publication date: 27 January 2009

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85097-7_7

zbMATH Keywords

branch-and-boundcomputational geometryapproximation algorithms\(k\)-centercontainmentgeometric inequalitiesSOCPcore-sets2-SATdiameter partition

Mathematics Subject Classification ID

Convex programming (90C25) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (3)

Smoothing and Regularization for Mixed-Integer Second-Order Cone Programming with Applications in Portfolio Optimization ⋮ Rational polyhedral outer-approximations of the second-order cone ⋮ On Subadditive Duality for Conic Mixed-integer Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering a set of points by two axis-parallel boxes
• Minimal containment under homothetics: a simple cutting plane approach
• A faster algorithm for the two-center decision problem
• Clustering to minimize the maximum intercluster distance
• Diameter partitioning
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• On the complexity of some basic problems in computational convexity. I. Containment problems
• More planar two-center algorithms
• A simple linear algorithm for computing rectilinear 3-centers
• Excursions into combinatorial geometry
• On the complexity of some geometric problems in unbounded dimension
• The 2-Center Problem with Obstacles
• Approximate clustering via core-sets
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solving the continuous space p-centre problem: planning application issues

This page was built for publication: New Algorithms for k-Center and Extensions