alt Hacker NewsOnce you admit approximations the theoretical problem trades places with a more interesting one: what is the Pareto frontier of loss vs complexity?
Once you admit approximations the theoretical problem trades places with a more interesting one: what is the Pareto frontier of loss vs complexity?
This is still a theoretical problem. Whether or not a particular problem class admits and approximation or an arbitrarily good approximation is often of theoretical interest.
One interesting example is metric TSP versus general TSP. We are used to traveling salesman problem on a map with distances that obey the triangle inequality. This admits an easy heuristic solution to an approximation factor of 2 (just do minimum spanning tree twice). However, nonmetric TSP is not approximable (to a constant factor of the optimal value in polynomial time (unless P=NP)).