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

DOI10.1007/S11590-017-1177-YzbMATH Open1404.90139arXiv1606.06421OpenAlexW2745052688MaRDI QIDQ1653283FDOQ1653283

Authors: Zuping Wu, Yong Xia, Shu Wang 

Publication date: 3 August 2018

Published in: Optimization Letters (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

semidefinite programmingapproximation algorithmconvex relaxationmaximin dispersion

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Covering a simplex by spheres: complexity and algorithms
• 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
• New approximation algorithms for weighted maximin dispersion problem with box or ball constraints
• A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
• Convex relaxations of the weighted maxmin dispersion problem
• On the ball-constrained weighted maximin dispersion problem
• A note on semi-definite programming relaxations of ball-constrained weighted maximin dispersion problems

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)