Covering a simplex by spheres: complexity and algorithms

DOI10.1007/S10898-022-01137-ZMaRDI QIDQ2162517zbMATH OpenOpenAlexFDO

Authors Tongli Zhang, Yong Xia

Publication date 8 August 2022

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-022-01137-z

zbMATH Keywords

maximin dispersionNP-hardsimplex covering

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Minimax problems in mathematical programming (90C47)

Recommendations

• On determining the cover of a simplex by spheres centered at its vertices
• The computational complexity and approximability of a series of geometric covering problems
• Algorithms for polytope covering and approximation
• On some polyhedra covering problems
• The complexity of the covering radius problem
• Complexities of efficient solutions of rectilinear polygon cover problems
• scientific article; zbMATH DE number 26590
• An efficient search algorithm for minimum covering polygons on the sphere
• New analysis of the sphere covering problems and optimal polytope approximation of convex bodies
• scientific article; zbMATH DE number 3909232

Cites work

• A Maxmin Location Problem
• A Parametric 1-Maximin Location Problem
• Analytical models for locating undesirable facilities
• Approximating the weighted maximin dispersion problem over an \(\ell _p\)-ball: SDP relaxation is misleading
• Convex relaxations of the weighted maxmin dispersion problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1466435 (Why is no real title available?)
• scientific article; zbMATH DE number 913711 (Why is no real title available?)
• New approximation algorithms for weighted maximin dispersion problem with box or ball constraints
• On determining the cover of a simplex by spheres centered at its vertices
• On the ball-constrained weighted maximin dispersion problem

Cited in

(7)

• New analysis of the sphere covering problems and optimal polytope approximation of convex bodies
• Spherical coverage verification
• Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
• On determining the cover of a simplex by spheres centered at its vertices
• A recursive algorithm for finding the minimum covering sphere of a polytope and the minimum covering concentric spheres of several polytopes
• Angle covers: algorithms and complexity
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey

Describes a project that uses

Uses Software

• CPLEX
• CVX

This page was built for publication: Covering a simplex by spheres: complexity and algorithms

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