Campus Event Calendar

Event Entry

What and Who

Between the metric and non metric facility location problems

Guy Kortsarz
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 9 July 2019
45 Minutes
E1 4


Usually facility location is described in two ways. First the metric case for which there is a constant approximation ratio, and the non-metric case that is equivalent to Set Cover.

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.


Daniel Vaz
--email hidden

Daniel Vaz, 07/03/2019 11:59 AM
Daniel Vaz, 07/02/2019 11:47 PM -- Created document.