TY - JOUR

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

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

AU - Ravi, R.

PY - 2014/8

Y1 - 2014/8

N2 - In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the k -robust model where the possible scenarios tomorrow are given by all demand-subsets of size k. In this paper, we give the following simple and intuitive template for k -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for k -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our k -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal-dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max-min problems of the form: "given a covering problem instance, which k of the elements are costliest to cover?" For the problems mentioned above, we show that their k -max-min versions have performance guarantees similar to those for the k -robust problems.

AB - In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the k -robust model where the possible scenarios tomorrow are given by all demand-subsets of size k. In this paper, we give the following simple and intuitive template for k -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for k -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our k -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal-dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max-min problems of the form: "given a covering problem instance, which k of the elements are costliest to cover?" For the problems mentioned above, we show that their k -max-min versions have performance guarantees similar to those for the k -robust problems.

KW - 68W25

KW - 90C27

KW - Mathematics Subject Classification: 05C85

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

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

U2 - 10.1007/s10107-013-0705-5

DO - 10.1007/s10107-013-0705-5

M3 - Article

AN - SCOPUS:84905585107

SN - 0025-5610

VL - 146

SP - 583

EP - 615

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -