Ask HN: What companies attack an NP-Hard problem as part of their core business?

1 points by jwco 14y ago ↗ HN

Another way to phrase this is, what is the intersection of the NP-hard problem space and the current business landscape?

A related question: how effective would one be to search for start-up ideas by looking for where NP-Hardness crops up in the real world?

Also, more pedagogically, maybe these answers may provide examples for explaining what NP-Hardness is to myself and others.

As for an example of a company whose core business is basically solving (or approximating solutions to) an NP-hard problem, how about Fedex? I've heard it's more appropriate to think of Fedex as an algorithms company that happens to do shipping rather than a shipping company. So is it fair to say their core business is solving, or finding approximate solutions to, instances of the "traveling businessman" problem?

Not sure if this question is well-posed exactly, so please help if my terminology or conceptual understanding is off.

2 comments

[ 3.9 ms ] story [ 11.4 ms ] thread

jdc 14y ago ↗

The field of problem solving that Fedex applies to routing packages is called operations research. As you may have noticed, this discipline can be used by companies with simple business models that want to improve efficiency or reduce risk. A good place to start would be the Wikipedia article.

http://en.wikipedia.org/wiki/Operations_research

jwco 14y ago ↗

Thanks but I am really interested in reading more about NP hardness in real world situations. Operations research may be a place to start but then my question becomes "Where does NP hardness arise in operations research?"

Here's an example of a creative way to interpret my original question: as xkcd implies, you might say eBay "solves" an NP hard problem http://xkcd.com/399/. Ebay doesn't solve the traveling salesman problem as it is normally posed in computer science, but it rephrased the problem statement in a useful way.