Approximation Algorithms for Facility Location and Clustering Problems
Khoa Trinh - University of Maryland, College Park
Friday, March 31, 2017, 12:00-1:00 pm
• You are subscribed to this talk through .
• You are watching this talk through .
• You are subscribed to this talk. (unsubscribe, watch)
• You are watching this talk. (unwatch, subscribe)
• You are not subscribed to this talk. (watch, subscribe)
Abstract

Facility Location (FL) problems are among the most fundamental problems in
combinatorial optimization. FL problems are also closely related to
Clustering problems. Generally, we are given a set of facilities, a set of
clients, and a symmetric distance metric on these facilities and clients.
The goal is to "open" the "best" subset of facilities, subject to certain
budget constraints, and connect all clients to the opened facilities so that
some objective function of the connection costs is minimized. In this
dissertation, we consider generalizations of classic FL problems. Since
these problems are NP-hard, we aim to find good approximate solutions in
polynomial time.

We study the classic $k$-median problem which asks to find a subset of at
most $k$ facilities such that the sum of connection costs of all clients to
the closest facility is as small as possible. Our main result is a
$2.675$-approximation algorithm for this problem. We also consider the
Knapsack Median (KM) problem which is a generalization of the $k$-median
problem. In the KM problem, each facility is assigned an opening cost. A
feasible set of opened facilities should have the total opening cost at most
a given budget. The main technical challenge here is that the natural LP
relaxation has unbounded integrality gap. We propose a $17.46$-approximation
algorithm 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 generalization of the $k$-center problem, which is
called the Knapsack Center (KC) problem and has a similar budget constraint
as in the KM problem. Here we want to minimize the maximum distance from any
client to its closest opened facility. The KC problem is well-known to be
$3$-approximable. However, the current approximation algorithms for KC are
deterministic and it is not hard to construct instances in which almost all
clients have the worst-possible connection cost. Unfairness also arises in
this context: certain clients may consistently get connected to distant
centers. We design a randomized algorithm which guarantees that the expected
connection cost of "most" clients will be at most $(1+2/e) \approx 1.74$
times the optimal radius and the worst-case distance remains the same. We
also obtain a similar result for the $k$-center problem: all clients have
expected approximation ratio about $1.592$ with a deterministic upper-bound
of $3$ in the worst case.

It is well-known that a few outliers (very distant clients) may result in a
very large optimal radius in the center-type problems. One way to deal with
this issue is to cover only some $t$ out of $n$ clients in the so-called
robust model. In this thesis, we give tight approximation algorithms for
both robust $k$-center and robust matroid center problems. We also introduce
a lottery model in which each client $j$ wants to be covered with
probability at least $p_j \in [0,1]$. We then provide randomized
approximation algorithms for center-type problems in this model which
guarantee the worst-case bounds of the robust model and slightly violate the
coverage and fairness constraints.

Several of our results for FL problems in this thesis rely on novel
dependent rounding schemes. We develop these rounding techniques in the
general setting and show that they guarantee new correlation properties.
Given the wide applicability of the standard dependent rounding, we believe
that our new techniques are of independent interests.

This talk is organized by Karthik Abinav Sankararaman