Hacker News Reader

There are polynomial-time approximation schemes for all those problems. Few of the NP-complete problems are both difficult to approximate and have practical use cases. 3SAT is the big exception.

View on HN

I don't know which airlines are packing one-dimensional bins :). In dimensions 2 and above, bin packing has no PTAS unless P=NP, and in particular it's hard to derive anything with an approximation ratio appreciably better than sqrt(num_dimensions)).

And the famous Steiner tree result holds only in highly structured metrics like the Euclidean plane and some minor generalizations. For general metrics there's a lower bound of around 1.01 unless P=NP.

Multi-dimensional bin packing in general does not have PTASes. However, for the constrained versions of the problem used in practice, PTASes and other tractable algorithms exist. Same with the STP - very difficult in non-Euclidean space, but all practical applications are in Euclidean spaces.

Steiner tree problems are particularly vexatious in that regard. Polynomial-time approximation only guarantees a solution at most 40% more expensive than optimal. When you're spending tens to hundreds of millions of dollars on an electrical grid, that's quite the differential.

Reply on news.ycombinator.com