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 -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 with a capacity , a set C of clients, a metric d over 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 is connected by at most 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.
All are welcome!