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

1 pointsby jwcohace 14 años2 comments

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

jdchace 14 años

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

jwcohace 14 años

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.