New algorithms for k-center and extensions

DOI10.1007/S10878-009-9226-9zbMATH Open1184.90133OpenAlexW2797707629MaRDI QIDQ849133FDOQ849133

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

computational geometryapproximation algorithmsbranch-and-boundcontainmentgeometric inequalitiesSOCPcore-sets2-SATdiameter partition

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• SeDuMi
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solving semidefinite-quadratic-linear programs using SDPT3
• Excursions into combinatorial geometry
• Clustering to minimize the maximum intercluster distance
• Covering a set of points by two axis-parallel boxes
• Solving the continuous space p-centre problem: planning application issues
• Approximate clustering via core-sets
• On the complexity of some geometric problems in unbounded dimension
• Zwei Extremalprobleme der Minkowski-Geometrie
• Approximate minimum enclosing balls in high dimensions using core-sets
• More planar two-center algorithms
• 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
• The 2-center problem with obstacles
• Minimal containment under homothetics: a simple cutting plane approach
• A faster algorithm for the two-center decision problem
• Diameter partitioning
• A simple linear algorithm for computing rectilinear 3-centers

Cited In (7)

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

Uses Software

• SeDuMi
• SDPT3

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Efficient algorithms for the one-dimensional \(k\)-center problem 👍 👎
• Enhancements to two exact algorithms for solving the vertex \(P\)-center problem 👍 👎
• An approximation algorithm for \(k\)-center problem on a convex polygon 👍 👎
• Approximation algorithms for a \(k\)-line center 👍 👎
• Un nuevo resultado sobre la complejidad del problema delP-centro 👍 👎
• New Algorithms for k-Center and Extensions 👍 👎

This page was built for publication: New algorithms for \(k\)-center and extensions

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