TY - GEN

T1 - Thresholded covering algorithms for robust and max-min optimization

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

AU - Ravi, R.

PY - 2010

Y1 - 2010

N2 - 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?"

AB - 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?"

UR - http://www.scopus.com/inward/record.url?scp=77955330979&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955330979&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14165-2_23

DO - 10.1007/978-3-642-14165-2_23

M3 - Conference contribution

AN - SCOPUS:77955330979

SN - 3642141641

SN - 9783642141645

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 262

EP - 274

BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings

T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010

Y2 - 6 July 2010 through 10 July 2010

ER -