Paper Info
Title
A polynomial-time approximation scheme for fault-tolerant distributed storage
Abstract
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 X generated by a known product distribution over {0, 1}n and a target value 0 ≤ θ ≤ 1, output a non-negative vector w, with ||w||1 ≤ 1, which maximizes the probability of the event w · X ≥ θ. 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 functions. 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.
Year
DOI
Venue
2013
10.1137/1.9781611973402.48
SODA
Keywords
DocType
Volume
algorithms,design,complexity measures and classes,general,approximation,theory
Journal
abs/1307.3621
ISBN
Citations 
PageRank 
978-1-61197-338-9
3
0.38
References 
Authors
29
5
Name
Order
Citations
PageRank
Constantinos Daskalakis1117985.25
Anindya De223924.77
Ilias Diakonikolas377664.21
Ankur Moitra489256.19
Rocco A. Servedio51656133.28