Complexity and approximation of the smallest \(k\)-enclosing ball problem

DOI10.1016/j.ejc.2015.02.011zbMath1315.05025OpenAlexW2138026666MaRDI QIDQ2346580

Vladimir Shenmaier

Publication date: 2 June 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2015.02.011

zbMATH Keywords

\((2 - \varepsilon)\)-inapproximability2-approximation algorithm

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorial aspects of finite geometries (05B25) Approximation algorithms (68W25)

Related Items (5)

Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ Approximation and complexity of the capacitated geometric median problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Iterated nearest neighbors and finding minimal polytopes
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Fast algorithms for computing the smallest \(k\)-enclosing circle
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• Optimal core-sets for balls
• Finding k points with minimum diameter and related problems
• `` Strong NP-Completeness Results
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Approximate minimum enclosing balls in high dimensions using core-sets

This page was built for publication: Complexity and approximation of the smallest \(k\)-enclosing ball problem