Skip to content

{ Category Archives } Research

Hey Buddy, Can I Sell You an NP Hard Problem?

In keeping with issues of economics and computational power, there is a very neat paper out of Princeton by Arora, Barak, Brunnermeier, and Ge entitled “Computational Complexity and Information Asymmetry in Financial Products“.  Can you embed an NP-hard problem into the pricing problem for a financial instrument?  As the authors point out, the answer is […]

P=NP in the New York Times

The New York Times has a nice article on the recent Communications of the ACM article on P=NP (article at author Lance Fortnow’s site). I had read Fortnow’s article last month, and really liked it. In fact, I am surprised I didn’t blog it: I guess I was too busy worrying about false proofs of […]

Graph Coloring Benchmark System

For many years, I have wanted to put together a system for keeping track of results in solving instances of various combinatorial optimization problems.  This started back in the early 1990s when I was the coordinator for the DIMACS Challenge on Cliques, Coloring, and Satisfiability.  This was pre-web, so everything was done via ftp and […]

Three City Traveling Salesman Problem Solved by Bacteria!

A Guardian (London) article has the provocative title “Bacteria make computers look like pocket calculators” (thanks Hamish for the pointer). They report on how bacteria can be used to search through feasible solutions to the traveling salesman problem to find optimal solutions: The research, published today in the Journal of Biological Engineering, proves that bacteria […]

P=NP …

… or not. About 20 years ago, I attended a summer program at RUTCOR (the OR center at Rutgers) called, I believe, ARIDAM (Advanced Research Institute in Discrete Applied Mathematics?  Something like that).  It was a great few weeks:  I learned a lot and met a number of people for the first time who I […]

The Perils of “Statistical Significance”

As someone who teaches data mining, which I see as part of operations research, I often talk about what sort of results are worth changing decisions over.  Statistical significance is not the same as changing decisions.  For instance, knowing that a rare event is 3 times more likely to occur under certain circumstances might be […]

Computational Sustainability

Carla Gomes from Cornell visited here a few weeks ago.  I have known Carla for a decade or so, and she has been one of the people who I have found very useful to talk to when trying to figure out the world of constraint programming. Carla gets involved in lots of things.  She (along […]

The Importance of Stupidity in (Operations) Research

A colleague of mine (thanks Laurie, I think!) sent me a copy of the paper “The Importance of Stupidity in Scientific Research” by Martin Schwartz, published in the Journal of Cell Science in 2008. My colleague swears I should not take offense, and no offense was taken. I think the article is brilliant. One of […]

Closed Loop Supply Chains

There is a new paper on the OR Forum by Dan Guide and Luk Van Wassenhove that looks at the research trajectory of “Closed Loops Supply Chains”.  Closed loop supply chains are supply chains where there is at least as much interest in getting things from the customer to the supplier as vice versa.  Sometimes […]

Solving real problems in Norway and Ireland

A couple of weeks ago, I was in Europe and visited two different (yet similar) research groups. The first was in Oslo, Norway, where I visited the applied math group at SINTEF. I think the best US analogy to SINTEF is the RAND Corporation, a name with cold-war connotations, but still very active in providing […]