Between the metric and non metric facility location problems

We identify a problem that is in between the two problems above. Say that the ratio of the maximum opening cost over the minimum service cost is theta (also called the slope). Then we show by a non standard analysis that a ratio of roughly ln theta-ln ln theta approximation holds in such a case. This ratio is quite small even for "huge" values of theta.

The paper is mostly conceptual. It shows how to convert a trivial alpha approximation, into a roughly ln alpha ratio if some axioms hold. We have many other applications. Some of which will be presented in the talk.

Joint work with Z. Nutov and E. Shason.