UB Theory Weekly – Week 1

Hi all,

The first Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:30 pm – A talk by Prof. Shi Li on “Approximating capacitated k-median with (1+eps)k open facilities”.

The abstract of the talk in his own words  – In the capacitated k-median (CKM) problem, we are given a set F of facilities, each facility i \in F with a capacity u_i,  a set C of clients, a metric d over F \cup C and an integer k.  The goal is to open k facilities in F and connect the clients C to the open facilities such that each facility i is connected by at most u_i clients, so as to minimize the total connection cost.

In this paper, we give the first constant approximation for CKM, that only violates the cardinality constraint by a factor of 1+eps. The natural LP relaxation for the problem, which almost all previous algorithms for CKM are based on, has unbounded integrality gap even if (2-eps)k facilities can be opened.  We introduce a novel configuration LP for the problem, that overcomes this integrality gap.  Our algorithm does not need to solve the configuration LP to optimality. Instead it is based on a rounding algorithm with the following property: given a fractional solution x, which may or may not be a valid solution to the LP, the rounding algorithm either successfully returns a good feasible solution, or reports a constraint of the LP that x violates.

4:30 – 4:45 pm – Q and A based on the talk.

4:45 – 5:00 pm – Socializing with the Theory community.

All are welcome!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s