Approximating the weighted maximin dispersion problem over an _p-ball: SDP relaxation is misleading

DOI10.1007/S11590-017-1177-YMaRDI QIDQ1653283zbMATH OpenOpenAlexFDO

Authors Zuping Wu, Yong Xia, Shu Wang

Publication date 3 August 2018

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06421

zbMATH Keywords

semidefinite programmingapproximation algorithmconvex relaxationmaximin dispersion

Mathematics Subject Classification ID

Semidefinite programming (90C22) Minimax problems in mathematical programming (90C47)

Abstract: Consider the problem of finding a point in a unit $n$-dimensional $el{l}_p$-ball ($pge2$) such that the minimum of the weighted Euclidean distance from given $m$ points is maximized. We show in this paper that the recent SDP-relaxation-based approximation algorithm [SIAM J. Optim. 23(4), 2264-2294, 2013] will not only provide the first theoretical approximation bound of $frac1-Oleft(sqrtln(m)/night)2$, but also perform much better in practice, if the SDP relaxation is removed and the optimal solution of the SDP relaxation is replaced by a simple scalar matrix.

Recommendations

• On the ball-constrained weighted maximin dispersion problem
• Convex relaxations of the weighted maxmin dispersion problem
• A note on semi-definite programming relaxations of ball-constrained weighted maximin dispersion problems
• New approximation algorithms for weighted maximin dispersion problem with box or ball constraints
• An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem

Cites work

• scientific article; zbMATH DE number 1466435 (Why is no real title available?)
• scientific article; zbMATH DE number 913711 (Why is no real title available?)
• A Maxmin Location Problem
• Approximating quadratic programming with bound and quadratic constraints
• Approximation algorithms and semidefinite programming.
• Convex relaxations of the weighted maxmin dispersion problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On maximization of quadratic form over intersection of ellipsoids with common center
• On the ball-constrained weighted maximin dispersion problem
• Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
• Semidefinite relaxation and nonconvex quadratic optimization

Cited in

(8)

• A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
• An efficient algorithm for nonconvex-linear minimax optimization problem and its application in solving weighted maximin dispersion problem
• An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem
• A note on semi-definite programming relaxations of ball-constrained weighted maximin dispersion problems
• New approximation algorithms for weighted maximin dispersion problem with box or ball constraints
• Covering a simplex by spheres: complexity and algorithms
• Convex relaxations of the weighted maxmin dispersion problem
• On the ball-constrained weighted maximin dispersion problem

Describes a project that uses

Uses Software

• CVX

This page was built for publication: Approximating the weighted maximin dispersion problem over an \(\ell _p\)-ball: SDP relaxation is misleading

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