New algorithms for \(k\)-center and extensions

DOI10.1007/s10878-009-9226-9zbMath1184.90133OpenAlexW2797707629MaRDI QIDQ849133

Lucia Roth, René Brandenberg

Publication date: 24 February 2010

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9226-9

zbMATH Keywords

branch-and-boundcomputational geometryapproximation algorithmscontainmentgeometric inequalitiesSOCPcore-sets2-SATdiameter partition

Mathematics Subject Classification ID

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

Related Items

A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems ⋮ Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion ⋮ SHARPENING GEOMETRIC INEQUALITIES USING COMPUTABLE SYMMETRY MEASURES ⋮ No dimension-independent core-sets for containment under homothetics ⋮ The 2-center problem in three dimensions ⋮ Speeding up the optimal method of Drezner for the \(p\)-centre problem in the plane ⋮ Minimal containment under homothetics: a simple cutting plane approach

Uses Software

• SeDuMi
• SDPT3

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• SeDuMi
• 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
• Zwei Extremalprobleme der Minkowski-Geometrie
• The 2-Center Problem with Obstacles
• Approximate clustering via core-sets
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solving the continuous space p-centre problem: planning application issues
• Approximate minimum enclosing balls in high dimensions using core-sets