Hacker News Reader

Comment by klyrs | Hacker News Reader

Many NP-complete problems and their Harder variants are in the realm of optimization. Packing boxes in air freight 1% tighter can have millions of dollars of practical consequences per year. Communications and electrical networks depend on the Steiner tree problem. Machine shops, restaurants, etc leave money on the table when their schedules are not well-optimized. I could go on and on.

View on HN

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.

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.

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.

yes but theoretical advancements in NP-complete problems very rarely turn into empirical improvements

It's not hard to see why this would be the case when the culture seems to start with the premise of "it's just ivory tower mathematics with no practical consequences"

If instead people were willing to set that hubris to the side and treat problems seriously then maybe we would see theoretical advancements be turned into empirical improvements with proper investment. Why would investment be made to operationalize theoretical advancement if the belief is that it's meaningless?

The entire reasoning of not treating these problems seriously from the start, then saying they rarely turn into empirical improvements... it all seems very self-fulfilling and circular.

Reply on news.ycombinator.com