Convex Relaxations of the Weighted Maxmin Dispersion Problem

DOI10.1137/120888880zbMath1295.90110OpenAlexW2057211359MaRDI QIDQ5408220

Jason L. Loeppky, Sheena Haines, Shawn Xianfu Wang, Paul Tseng

Publication date: 9 April 2014

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120888880

zbMATH Keywords

approximation algorithmNP-hardsemidefinite programming relaxationsecond-order cone programming relaxationweighted maxmin dispersion problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (10)

On the Ball-Constrained Weighted Maximin Dispersion Problem ⋮ Approximating the weighted maximin dispersion problem over an \(\ell _p\)-ball: SDP relaxation is misleading ⋮ Covering a simplex by spheres: complexity and algorithms ⋮ A stochastic primal-dual method for a class of nonconvex constrained optimization ⋮ A survey of hidden convex optimization ⋮ Exact Second-Order Cone Programming Relaxations for Some Nonconvex Minimax Quadratic Optimization Problems ⋮ 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 ⋮ Exact dual bounds for some nonconvex minimax quadratic optimization problems ⋮ New approximation algorithms for weighted maximin dispersion problem with box or ball constraints

This page was built for publication: Convex Relaxations of the Weighted Maxmin Dispersion Problem