In theoretical CS we often take NP-complete as a sign to stop searching for an efficient algorithm. Optimization people take NP-complete as a starting point, using powerful algorithmic ideas, clever heuristics and sheer computing power to solve or nearly optimize in many real-world cases.
Bill Cook talked about his adventures with the traveling salesman problem. Check out his British pub crawl and his tour through the nearly 50,000 US historic sites.
Michael Trick talked about his side job, schedule MLB baseball games, a surprisingly challenging problem. Like TSP, you want to minimize total travel distance but under a wide variety of constraints. "There's something satisfying about being at a bar, seeing a game on the TV and knowing those two teams are playing because you scheduled them." Can't say I've had that kind of satisfaction in my computational complexity research.
I've expressed in other comments on your blogs that I want to learn exactly how they schedule MLB games! I remember when I was 8 years old, the Orioles were playing the Cubs at camden yards. This was in all likelihood my first time seeing the Orioles play the cubs (considering my young age). So I asked my father "How do they decide who the Orioles play? How come they never play the Cubs but always play the Yankees and Red Sox?" He responded, "Well computers do it all son." My reply at the time was something along the lines of "That magical device in our family room that I play games on makes the schedule for the Orioles??? You're kidding!".
ReplyDeleteMr Trick sounds like a gentleman I want to talk to! Given 30 MLB teams I would love to understand the algorithm that goes into scheduling the appropriate teams to play one another taking into account efficient times for travel. I think its funny how we can make a schedule for all those MLB teams in a very balanced fashion (i.e. 18 games for each divisional opponent, 9 home 9 away etc) but cannot solve the Traveling Salesman problem. And you probably know baseball commentators are always saying that the schedules are sometimes really cruel. For example, A team playing the Sunday Night game on ESPN should NOT have to play a game the next night in a new city on a road trip after arriving in said city at 4 in the morning.