Skip to content

{ Category Archives } Research

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

That’s got to be true… doesn’t it?

Back in 1996, Harvey Greenberg, longtime faculty member at the University of Colorado at Denver, began putting together a collection of myths and counterexamples in mathematical programming.  While generally I find mathematical programming to be quite intuitive, there turn out to be lots of things that I think must be true that are not.  Consider […]

Postdocs and Special Year at the IMA

In 1987-88, I spent a great year in Minneapolis as a postdoc at the Institute for Mathematics and its Applications (and this picture of me comes from that time). Every year at the IMA has a special theme, and the theme my year was “Applied Combinatorics”. There were about a dozen of us postdocs that […]

The Sexiness of Integer Programming

Suresh Venkatasubramanian, of the excellent Geomblog, is at SODA and covered some preconference conferences. When covering a paper that used integer programming (via CPLEX), his comment was: It’s not the “sexiest” thing in the world to solve algorithms problems in practice by using large industrial strength packages. Oh, he didn’t say that, did he? I […]

Some Older but Perhaps Useful Notes on Networks and Matchings

More than 20 years ago, I was a postdoc at the Institut für Ökonometrie und Operations Research at the University of Bonn, an Institute headed by Prof. Bernhard Korte (who now heads Bonn’s Research Institute for Discrete Mathematics).  It was a fantastic year.  Also visiting that year were people like Bill Cunningham, Bill Cook, Andras […]

Bus Bunching talk at INFORMS

New post at the INFORMS site: “Avoiding Bunches of Buses”: While the INFORMS conference is big enough to stay within a narrow research area, it is also a great place to get inspiration outside your focus.  I hopped in to see a talk given by Don Eisenstein on work he has done with John Bartholdi […]

A New Approach to MaxFlow?

The MIT public relations office is reporting a new result on the maximum flow problem.  It appears that work by Kelner, Madry, Christiano, Spielman and Teng (in some permutation:  not surprisingly, the MIT release stresses the MIT authors) has reduced the complexity of maxflow to (V+E)^4/3 (from (V+E)^3/2.  Details are pretty sketchy, but the approach […]

Definitive Word on P!=NP Paper

Lance Fortnow of the blog Computational Complexity has, I believe, the definitive word on the P!=NP paper by Deolalikar (saying in a sentence what I couldn’t quite manage in two pages): Proving P  ≠ NP will require pure genius but you shouldn’t need a Fields medalist to verify the proof. Secondary message:  a good way to […]

P versus NP and the Research Process

By now, everyone in computer science and operations research is aware of the purported P<>NP proof of Vinay Deolalikar of HP Labs.  After intense discussion (mainly through blogs and wikis), the original paper was taken down, and Vinay has prepared a new version for submission.  He claims: I have fixed all the issues that were […]

Algorithmic Voting Theory, Venice, and a Talk on Old/New Papers

I just got back from Venice, where I attended a conference on Algorithmic Decision Theory.  This is a new conference series (optimistically numbered the first conference, implying at least a second) revolving around issues in uncertainty in decision making, preference solicitation, learning and other issues.  From the conference web page: A new unique event aiming […]