BEGIN:VCALENDAR
PRODID;X-RICAL-TZSOURCE=TZINFO:-//com.denhaven2/NONSGML ri_cal gem//EN
CALSCALE:GREGORIAN
VERSION:2.0
BEGIN:VTIMEZONE
TZID;X-RICAL-TZSOURCE=TZINFO:US/Eastern
BEGIN:DAYLIGHT
DTSTART:20170312T020000
RDATE:20170312T020000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DTEND;TZID=US/Eastern;VALUE=DATE-TIME:20170331T130000
DTSTART;TZID=US/Eastern;VALUE=DATE-TIME:20170331T120000
DESCRIPTION:Facility Location (FL) problems are among the most fundamenta
l problems incombinatorial optimization. FL problems are also closely re
lated toClustering problems. Generally\, we are given a set of facilitie
s\, a set ofclients\, and a symmetric distance metric on these facilitie
s and clients.The goal is to "open" the "best" subset of facilities\, su
bject to certainbudget constraints\, and connect all clients to the open
ed facilities so thatsome objective function of the connection costs is
minimized. In thisdissertation\, we consider generalizations of classic
FL problems. Sincethese problems are NP-hard\, we aim to find good appro
ximate solutions inpolynomial time.We study the classic $k$-median probl
em which asks to find a subset of atmost $k$ facilities such that the su
m of connection costs of all clients tothe closest facility is as small
as possible. Our main result is a$2.675$-approximation algorithm for thi
s problem. We also consider theKnapsack Median (KM) problem which is a g
eneralization of the $k$-medianproblem. In the KM problem\, each facilit
y is assigned an opening cost. Afeasible set of opened facilities should
have the total opening cost at mosta given budget. The main technical c
hallenge here is that the natural LPrelaxation has unbounded integrality
gap. We propose a $17.46$-approximationalgorithm for the KM problem. We
also show that\, after a preprocessing step\,the integrality gap of the
residual instance is bounded by a constant.The next problem is a genera
lization of the $k$-center problem\, which iscalled the Knapsack Center
(KC) problem and has a similar budget constraintas in the KM problem. He
re we want to minimize the maximum distance from anyclient to its closes
t opened facility. The KC problem is well-known to be$3$-approximable. H
owever\, the current approximation algorithms for KC aredeterministic an
d it is not hard to construct instances in which almost allclients have
the worst-possible connection cost. Unfairness also arises inthis contex
t: certain clients may consistently get connected to distantcenters. We
design a randomized algorithm which guarantees that the expectedconnecti
on cost of "most" clients will be at most $(1+2/e) \\approx 1.74$times t
he optimal radius and the worst-case distance remains the same. Wealso o
btain a similar result for the $k$-center problem: all clients haveexpec
ted approximation ratio about $1.592$ with a deterministic upper-boundof
$3$ in the worst case.It is well-known that a few outliers (very distan
t clients) may result in avery large optimal radius in the center-type p
roblems. One way to deal withthis issue is to cover only some $t$ out of
$n$ clients in the so-calledrobust model. In this thesis\, we give tigh
t approximation algorithms forboth robust $k$-center and robust matroid
center problems. We also introducea lottery model in which each client $
j$ wants to be covered withprobability at least $p_j \\in [0\,1]$. We th
en provide randomizedapproximation algorithms for center-type problems i
n this model whichguarantee the worst-case bounds of the robust model an
d slightly violate thecoverage and fairness constraints.Several of our r
esults for FL problems in this thesis rely on noveldependent rounding sc
hemes. We develop these rounding techniques in thegeneral setting and sh
ow that they guarantee new correlation properties.Given the wide applica
bility of the standard dependent rounding\, we believethat our new techn
iques are of independent interests.
URL:https://talks.cs.umd.edu/talks/1736
SUMMARY:Khoa Trinh - Approximation Algorithms for Facility Location and C
lustering Problems
LOCATION:3258 AVW
END:VEVENT
END:VCALENDAR