Thresholded covering algorithms for robust and max-min optimization

Anupam Gupta, Viswanath Nagarajan, R. Ravi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The general problem of robust optimization is this: one of several possible scenarios will appear tomorrow and require coverage, but things are more expensive tomorrow than they are today. What should you anticipatorily buy today, so that the worst-case covering cost (summed over both days) is minimized? We consider the k-robust model [6,15] where the possible scenarios tomorrow are given by all demand-subsets of size k. We present a simple and intuitive template for k-robust problems. This gives improved approximation algorithms for the k-robust Steiner tree and set cover problems, and the first approximation algorithms for k-robust Steiner forest, minimum-cut and multicut. As a by-product of our techniques, we also get approximation algorithms for k-max-min problems of the form: "given a covering problem instance, which k of the elements are costliest to cover?"

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Number of pages13
EditionPART 1
StatePublished - 2010
Event37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France
Duration: Jul 6 2010Jul 10 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6198 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other37th International Colloquium on Automata, Languages and Programming, ICALP 2010

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Thresholded covering algorithms for robust and max-min optimization'. Together they form a unique fingerprint.

Cite this