Local Search for Max-Sum Diversification

Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen

We provide simple and fast polynomial time approximation schemes (PTASs) for several variants of the max-sum diversification problem which, in its most basic form, is as follows: G…