Skip to content

{ Monthly Archives } January 2012

Car Talk and TSP Paths

On the suddenly hot topic of the Traveling Salesman Problem (see here and here), this week’s Car Talk puzzle is a TSP-like problem (though it is really a graph theory problem: the hamiltonian path problem to be exact). The company that Bobo works for just finished a new product. They wanted to promote it across […]

A Love Letter to the Traveling Salesman Problem

Bill Cook of Georgia Tech has a new book out on the Traveling Salesman Problem entitled “In Pursuit of the Traveling Salesman” from Princeton University Press (or from Amazon or B&N).  Unlike his previous book (with David Applegate, Bob Bixby and Vašek Chvátal), this book is aimed at a general audience. Bill takes his readers down a […]

Death to Data Hogs! Ooops, that’s us!

The New York Times has an article on the concentration of use of mobile airwaves.  It seems that 1% of the users consume half the bandwidth: The world’s congested mobile airwaves are being divided in a lopsided manner, with 1 percent of consumers generating half of all traffic. The top 10 percent of users, meanwhile, are […]

16 Clue Sudokus

I am sure everyone has seen Sudoku puzzles:  it was quite a fad a few years ago.  The puzzle begins with an 9×9 grid, partially filled with numbers from 1 to 9 (the “givens”).  The goal is to complete the grid so that that every row, column, and the nine 3×3 subgrids in the corners […]

Super Exciting News on Super Polynomiality of LP Formulations of the TSP Polytope

Years ago, I spent a very pleasant couple of weeks in a group debunking a claimed linear programming formulation of the Traveling Salesman Problem.  I wrote on this before, and bewailed the fact that I was not smart enough to figure out there was a general theorem there:  Yannakakis showed that no symmetric linear programming formulation […]

The Perils of Search Engine Optimization

This blog has been around more than six years, making it ancient in the blogosphere.  And, while not popular like the big-boy blogs (I run about 125,000 hits a year with about 1500 RSS subscribers according to FeedBurner), I think I have a reasonable-sized audience for the specialized topic I cover (operations research, of course!). […]

Cure for the Winter Blues

The weather here in Pittsburgh is finally feeling more like winter: it is a dreary, windy day, with intermittent snow. I suspect it will only get worse over the next two months. Fortunately I know a cure for the winter blues: Optimization! Optimization with the INFORMS crowd, that is, at the Fourth INFORMS Optimization Society […]

Operations Research Resolutions for 2012

It is the time of the year for resolutions.  Resolutions help define what we would like to be, but are damned hard things to follow through on.  As Paul Rubin points out, gyms will be overrun for a few weeks with “resolvers” (or, as my former personal trainer called them “resolutionists”) before the weight room […]