Wednesday, 15:15 - 15:40 h, Room: H 3010


Viswanath Nagarajan
Thresholded covering algorithms for robust and max-min optimization

Coauthors: Anupam Gupta, R. Ravi


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:

  1. The k-max-min version of P asks for k (out of n) demands that are the costliest to cover.
  2. 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.


Talk 1 of the invited session Wed.3.H 3010
"Randomized rounding algorithms in mathematical programming" [...]
Cluster 1
"Approximation & online algorithms" [...]


  personal loans online . In rare cases, the smarting in eyes, the tumefaction of eyelids, nausea and headaches can happen. In case of long term Levitra Soft online administration the side effects become less perceptible or disappear at all.