Skip to content

{ Category Archives } Research

Complete Enumeration Arguments Deemed Harmful…

… or “The Traveling Salesman Problem is Not That Hard”. When I talk to people about what I do for a living, I often face blank stares (or, worse, rapidly retreating backs) when I describe problems like the Traveling Salesman Problem. Me: “Well, suppose the dots on this napkin represent cities, and you want to […]

Quantum computing and operations research

Quantum computing is one of those weird ideas out there that will either change the world or go the way of  cold fusion, so I periodically think I need to learn more about the area. I am by no means an expert (or even knowledgeable) in the area.  My expertise comes from reading Scott Aaronson’s blog, […]

Summer Internship at IBM Research, AI for Optimization Group

Just saw this announcement of a summer internship A summer internship position is available for 2013 in the “AI for Optimization” group within the Business Analytics and Mathematical Sciences department at IBM Watson Research Center, Yorktown Heights, New York.  The internship will last for about 3 months and will be scheduled between March and October, […]

Easy and Hard Problems in Practice

David Eppstein of the blog 0xde has a list of his top 10 preprints in algorithms in 2012.  One particularly caught my eye: Clustering is difficult only when it does not matter, Amit Daniely, Nati Linial, and Michael Saks,  arXiv:1205.4891. […] this represents a move from worst-case complexity towards something more instance-based. The main idea […]

Referees considered harmful

When doing empirical work, researchers often mess up either in the design of the experiment or in the analysis of data.  In operations research, much of our “empirical work” is in computational testing of algorithms.  Is algorithm A faster than algorithm B?  “It depends” is generally the only honest answer.  It depends on the instance […]

The cutting plane method for matching is polynomial

Michael Mitzenmacher is a computer scientist at Harvard with a blog My Biased Coin.  As you might expect from the title, Michael works in the area of randomized algorithms, and even has a book on the subject.  His blog is an extremely useful guide to the what is happening in algorithms in CS (and what […]

Fischetti Speeds Up Optimization with Randomness

I just got back from a very nice workshop on “Matheuristics” held outside of Rio de Janeiro, Brazil.  Matheuristics is the combination of optimization and heuristics.  For instance, I talked about large scale local search for sports scheduling problems (among other things).  In this approach, portions of a sports schedule are fixed, and you optimize […]

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 […]

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 […]