[andrewljohnson]

Great commentary about the actual ramifications of NP problems.

This reminds me of a company I used to do some marketing work - CombineNet. They would basically take a large, multi-participant marketplace (for example, several hospitals buying a billion dollars in goods from pharma companies and medical device manufacturers).

CombineNet's technology wouldn't guarantee the optimal buy to the hospitals, but it usually could, and in the cases that it couldn't, it could get very close to optimal and specify how close the answer was. I'm not a mathematician, but I think they were solving a "clearing problem?"

Coincidentally, the founder of CombineNet was a professor at the same school as Herb Simon... Carnegie Mellon.

Sandholm also wrote a heads-up Texas Hold'em bot that derived its strategy from the rules, and beat a ton of other heads-up poker bots handily. I think articles about this showed up on HN a while back: http://portal.acm.org/citation.cfm?id=1402350

[MaysonL]

For those without acm access, also available at http://www.cs.cmu.edu/~sandholm/texas.aaai06.pdf