Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Between the metric and non metric facility location problems
Speaker:Guy Kortsarz
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 9 July 2019
Duration:45 Minutes
Building: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.

Name(s):Daniel Vaz
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Daniel Vaz, 07/03/2019 11:59 AM
  • Daniel Vaz, 07/02/2019 11:47 PM -- Created document.