MWU 2.0 with Approximation Guarantee for the Distance Geometry Problem

In this short paper, we define an approximation guaranteed algorithm for Distance Geometry Problem (DGP), by straightforwardly extending the framework proposed by Plotkin, Shmoys, and Tardos for fractional packing and covering problems. In particular, following the approach in Arora et al. [1], we adapt the Multiplicative Weights Update (MWU) framework to define an approximated algorithm which calls an oracle solving the surrogate relaxation of the feasibility problem a polynomial number of times. We implemented the algorithm and we present promising computational results in terms of mean and largest error of the produced solutions. We compare the new algorithm with the previous version of MWU for DGP introduced in Mencarelli et al. [9].