[Colloquium] Reminder: Demirci/MS Presentation/Jun 13, 2016

[Margaret Jaffey]

This is a reminder about Gokalp's MS Presentation on Monday morning.

------------------------------------------------------------------------------
Date:  Monday, June 13, 2016

Time:  9:00 AM

Place:  Ryerson 277

M.S. Candidate:  Gokalp Demirci

M.S. Paper Title: Constant Approximation for Capacitated k-Median with
(1+epsilon)-Capacity Violation

Abstract:
In the classical k-Median problem, the input consists of a set of
facilities and a set of clients on a metric space and a number k.
We're asked to open a subset of at most k facilities and assign each
client to an open facility. The goal is to minimize the total distance
of connections between clients and their assigned facilities. We study
the Capacitated k-Median problem where we have the extra constraints
limiting the number of clients that can be connected to each facility
by the capacity of that facility specified in the input. Existing
constant-factor approximation algorithms for the Capacitated k-Median
problem are all pseudo-approximations that violate either the
capacities or the upper bound k on the number of open facilities.
Using the natural linear program relaxation for the problem, one can
only hope to get the violation factor down to 2 for constant-factor
approximations. Li [SODA'16] introduced a novel LP to go beyond the
limit of 2 and gave a constant-factor approximation algorithm that
opens (1+\epsilon)k facilities.

We use the configuration LP of Li [SODA'16] to give a constant-factor
approximation for the Capacitated k-Median problem in a seemingly
harder configuration: we violate only the capacities by 1+\epsilon.
This result settles the problem as far as pseudo-approximation
algorithms are concerned.

Gokalp's advisor is Prof. Janos Simon

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_announcements#demirci

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=