Chebyshev center of the intersection of balls: complexity, relaxation and approximation

• 成果类型: Article
• 署名作者: Xia, Yong; Yang, Meijia; Wang, Shu
• 署名单位: Beihang University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01479-0
• 发表日期: 2021
• 页码: 287-315
• 关键词: nonconvex quadratic optimization; algorithms; bounds

摘要

We study the n-dimensional problem of finding the smallest ball enclosing the intersection of p given balls, the so-called Chebyshev center problem (CCB). It is a minimax optimization problem and the inner maximization is a uniform quadratic optimization problem (UQ). When p = n, (UQ) is known to enjoy a strong duality and consequently (CCB) is solved via a standard convex quadratic programming (SQP). In this paper, we first prove that (CCB) is NP-hard and the special case when n = 2 is polynomially solvable. With the help of a newly introduced linear programming relaxation (LP), the (SQP) relaxation is reobtained more directly and the first approximation bound for the solution obtained by (SQP) is established for the hard case p > n. Finally, also based on (LP), we showthat (CCB) is polynomially solvablewhen either n or p-n(> 0) is fixed.