The intrinsic hardness of structure approximation

A natural question when dealing with problems that are computationally hard to solve is whether it is possible to compute a solution which is close enough to the optimal solution for practical purposes. The usual notion of "closeness" is that the value of the solution is not far from the optimal value. In this M.Sc thesis, we will focus on the generalization of this notion where closeness is defined with respect to a given distance function. This framework, named "Structure approximation", was introduced in 2007 paper by Hamilton, Müller, van Rooij and Wareham [HMvRW07], who posed the question of complexity of approximation of NP-hard optimization problems in this setting. In this thesis, we will survey what is known about the complexity of structure approximation, in particular recasting results on Hamming approximation of NP witnesses in the Hamilton/Müller/van Rooij/Wareham framework. Specifically, the lower bounds in the NP witness setting imply that at least for some natural choices of the distance function any non-trivial structure approximation is as hard to compute as an exact solution to the original problem. In particular, results of Sheldon and Young (2013) state, in the language of structure approximation, that it is not possible to compute more than n/2 + nᵋ bits of an optimal solution correctly in polynomial time without being able to solve the original problem in polynomial time. Moreover, for some problems and solution representations, even a polynomial-time algorithm for finding η/2−O([root of]η ln η) bits of an optimal solution can be used to solve the problem exactly in polynomial time. In addition to the lower bounds results, we will discuss algorithms and design techniques that can be used to achieve some degree of structure approximation for several well-known problems, and look at some traditional approximation algorithms to see whether the approximate solution they provide is also a structure approximation. We make a number of observations throughout the thesis, in particular extending Hamming approximation lower bounds to edit distance approximation with the same n/2 + nᵋ parameters for several problems. Finally, we apply these techniques to analyse the structure approximation complexity of the Phrase Alignment problem in linguistics, in particular Weighted Sentence Alignment (WSA) problem of DeNero and Klein [DK08]. We discuss several ways of defining a natural witness for this problem and their implications for its structure approximability. In a search of the most compact natural witness representation, we define a still NP-hard restriction of the WSA, a Partition Weighted Sentence Alignment, and show that the n/2 + nᵋ lower bounds for the Hamming distance and edit distance apply in this case; this implies structure inapproximability of the WSA itself with somewhat weaker parameters