UB Theory Weekly – Week 24

Hi all,

The 24th Theory Weekly Meeting will happen this Friday between 2:00 – 3:00 pm at 203 Davis Hall (Theory Lab). The schedule will be as follows :

2:00 – 3:00 pm – A talk by Shi Li on his recent FOCS 2016 paper: Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions.

Advertisements

UB Theory Weekly – Week 10

Hi all,

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

4:00 – 4:50 pm – A talk by Shi Li. The abstract of the talk in his own words –

I will talk about the classic 3/2-approximation for the scheduling problem to minimize the total weighted competition time.

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

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!