Multidimensional Scaling: Approximation and Complexity
  Metric Multidimensional scaling (MDS) is a classical method for generating
meaningful (non-linear) low-dimensional embeddings of high-dimensional data.
MDS has a long history in the statistics, machine learning, and graph drawing
communities. In particular, the Kamada-Kawai force-directed graph drawing
method is equivalent to MDS and is one of the most popular ways in practice to
embed graphs into low dimensions. Despite its ubiquity, our theoretical
understanding of MDS remains limited as its objective function is highly
non-convex. In this paper, we prove that minimizing the Kamada-Kawai objective
is NP-hard and give a provable approximation algorithm for optimizing it, which
in particular is a PTAS on low-diameter graphs. We supplement this result with
experiments suggesting possible connections between our greedy approximation
algorithm and gradient-based methods.
