Thresholded covering algorithms for robust and max-min optimization

Anupam Gupta, Viswanath Nagarajan, R. Ravi

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

Abstract

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
Pages262-274
Number of pages13
EditionPART 1
DOIs
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

Other

Other37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Country/TerritoryFrance
CityBordeaux
Period7/6/107/10/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this