Sariel Har-Peled talked about the interface between Operations Research and low-dimensional geometry. The bottom line is that there is a ton of problems from OR that one can restrict for the case of low-dimensions, and they are pretty much largely unanswered or unaddressed. Primarily, he said, because they usually require tools from both ends. Here’s one that he discussed in detail.

Discrete unit-circle cover in the plane

A problem instance is given by a set of points in the plane and a set of unit discs. The goal is to find the smallest subset of the discs that covers all points. This problem is NP-complete (surprisingly). The open question is: Can you -approximate the optimum (for any )?

Bicriteria unit-circle cover in the plane

My recollection on this one may be slightly off. It’s the same problem as above, but you are shooting for a bicriteria algorithm where you are allowed to expand the given discs by a small , so the bicriteria is in . The question here may have been, what is the smallest disc expansion for which you can get a bicriteria solution equal to the optimum (without disc expansion).