TY - GEN

T1 - A polynomial-time approximation scheme for fault-tolerant distributed storage

AU - Daskalakis, Constantinos

AU - De, Anindya

AU - Diakonikolas, Ilias

AU - Moitra, Ankur

AU - Servedio, Rocco A.

PY - 2014

Y1 - 2014

N2 - We consider a problem which has received considerable attention in systems literature because of its applications to routing in delay tolerant networks and replica placement in distributed storage systems. In abstract terms the problem can be stated as follows: Given a random variable χ generated by a known product distribution over {0,1}n and a target value 0 ≤ θ ≤ 1, output a non-negative vector ω, with ||ω||1 ≤ 1, which maximizes the probability of the event ω χ ≥ θ. This is a challenging non-convex optimization problem for which even computing the value Pr[w·X > θ] of a proposed solution vector w is#P-hard. We provide an additive EPTAS for this problem which, for constant-bounded product distributions, runs in poly(n) · 2Poly(1/ε) time and outputs an ε-approximately optimal solution vector w for this problem. Our approach is inspired by, and extends, recent structural results from the complexity-theoretic study of linear threshold func-tions. Furthermore, in spite of the objective function being non-smooth, we give a unicriterion PTAS while previous work for such objective functions has typically led to a bicriterion PTAS. We believe our techniques may be applicable to get unicriterion PTAS for other non-smooth objective functions.

AB - We consider a problem which has received considerable attention in systems literature because of its applications to routing in delay tolerant networks and replica placement in distributed storage systems. In abstract terms the problem can be stated as follows: Given a random variable χ generated by a known product distribution over {0,1}n and a target value 0 ≤ θ ≤ 1, output a non-negative vector ω, with ||ω||1 ≤ 1, which maximizes the probability of the event ω χ ≥ θ. This is a challenging non-convex optimization problem for which even computing the value Pr[w·X > θ] of a proposed solution vector w is#P-hard. We provide an additive EPTAS for this problem which, for constant-bounded product distributions, runs in poly(n) · 2Poly(1/ε) time and outputs an ε-approximately optimal solution vector w for this problem. Our approach is inspired by, and extends, recent structural results from the complexity-theoretic study of linear threshold func-tions. Furthermore, in spite of the objective function being non-smooth, we give a unicriterion PTAS while previous work for such objective functions has typically led to a bicriterion PTAS. We believe our techniques may be applicable to get unicriterion PTAS for other non-smooth objective functions.

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

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

U2 - 10.1137/1.9781611973402.48

DO - 10.1137/1.9781611973402.48

M3 - Conference contribution

AN - SCOPUS:84902096390

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 628

EP - 644

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -