## Invited Session Wed.3.H 3010

#### Wednesday, 15:15 - 16:45 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Randomized rounding algorithms in mathematical programming

**Chair: Maxim Sviridenko**

**Wednesday, 15:15 - 15:40 h, Room: H 3010, Talk 1**

**Viswanath Nagarajan**

Thresholded covering algorithms for robust and max-min optimization

**Coauthors: Anupam Gupta, R. Ravi**

**Abstract:**

We consider combinatorial covering problems (eg. Set cover, Steiner forest and Multicut) in the context of "robust'' and "max-min'' optimization. Given an instance of a covering problem *P* with *n* demands and parameter *k*:

- The k-max-min version of
*P* asks for *k* (out of *n*) demands that are the costliest to cover.

- The
*k*-robust version of *P* is a two-stage optimization problem, where an arbitrary subset *D* of *k* demands materializes in the second stage. Elements (that cover demands) are more expensive in the second stage than the first. The objective is to anticipatorily purchase some elements in the first stage, so as to minimize the worst-case covering cost (sum of both stages) over all possible demands *D*.

We present an algorithmic template that achieves nearly tight approximation guarantees for

*k*-robust and

*k*-max-min versions of many covering problems. The analysis is based on establishing certain net-type properties, that rely on LP dual-rounding and primal-dual arguments.

**Wednesday, 15:45 - 16:10 h, Room: H 3010, Talk 2**

**Sungjin Im**

Preemptive and non-preemptive generalized min sum set cover

**Coauthors: Maxim Sviridenko, Ruben van der Zwaan**

**Abstract:**

In the Preemptive Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets {S_{1}, S_{2}, ..., S_{m}} where each subset S_{i} of ground elements has a positive requirement k_{i} that has to be fulfilled. We would like to preemptively order (schedule) all elements to minimize the total cover time of all sets S_{i}. The cover time of set S_{i} is defined as the first time when k_{i} amount of elements in S_{i} are scheduled. We give a 2-approximation for this problem, which is tight under a certain complexity assumption. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive version of this problem. A key technical ingredient of our results is a novel linear programming relaxation which is completely different from [Bansal-Gupta-Krishnaswamy 10], [Skutella-Williamson 11]. We also show that our relaxation is stronger than the previous one.

**Wednesday, 16:15 - 16:40 h, Room: H 3010, Talk 3**

**Aravind Srinivasan**

Dependent rounding and its applications

**Abstract:**

Randomized rounding is a well-known and powerful tool in rounding solutions to relaxations of optimization problems. Starting with the work of Ageev and Sviridenko, the notion of dependent randomized rounding has led to significant progress in a variety of (approximation) algorithms: one carefully defines dependencies between several basic random variables in the rounding process. We will present a brief survey of this area, including works of the speaker and those of Calinescu, Chekuri, Pal and Vondrak.