New Algorithms for k-Center and Extensions

DOI10.1007/978-3-540-85097-7_7MaRDI QIDQ5505644zbMATH OpenOpenAlexFDO

Authors 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

2-SAT\(k\)-centerapproximation algorithmsbranch-and-boundcomputational geometrycontainmentcore-setsdiameter partitiongeometric inequalitiesSOCP

Mathematics Subject Classification ID

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

Recommendations

• New algorithms for \(k\)-center and extensions
• No dimension independent core-sets for containment under homothetics
• Solving \(k\)-center problems involving sets based on optimization techniques
• An approximation algorithm for k-center problem on a convex polygon
• No dimension-independent core-sets for containment under homothetics

Cites work

• A faster algorithm for the two-center decision problem
• A simple linear algorithm for computing rectilinear 3-centers
• Approximate clustering via core-sets
• Clustering to minimize the maximum intercluster distance
• Covering a set of points by two axis-parallel boxes
• Diameter partitioning
• Excursions into combinatorial geometry
• scientific article; zbMATH DE number 4200003 (Why is no real title available?)
• scientific article; zbMATH DE number 41467 (Why is no real title available?)
• scientific article; zbMATH DE number 3469876 (Why is no real title available?)
• scientific article; zbMATH DE number 3579840 (Why is no real title available?)
• scientific article; zbMATH DE number 1303609 (Why is no real title available?)
• scientific article; zbMATH DE number 6472586 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Minimal containment under homothetics: a simple cutting plane approach
• More planar two-center algorithms
• On the complexity of some basic problems in computational convexity. I. Containment problems
• On the complexity of some geometric problems in unbounded dimension
• Solving the continuous space p-centre problem: planning application issues
• The 2-center problem with obstacles
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(7)

• Rational polyhedral outer-approximations of the second-order cone
• A mixed breadth-depth first strategy for the branch and bound tree of Euclidean k-center problems
• Smoothing and regularization for mixed-integer second-order cone programming with applications in portfolio optimization
• On Subadditive Duality for Conic Mixed-integer Programs
• Minimal containment under homothetics: a simple cutting plane approach
• No dimension independent core-sets for containment under homothetics
• 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 Q5505644)