کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142446 | 957149 | 2014 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A fully polynomial-time approximation scheme for approximating a sum of random variables
ترجمه فارسی عنوان
یک تقریب به طور کامل چندجملهای برای تقریب یک مجموع متغیرهای تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given nn independent integer-valued random variables X1,X2,…,XnX1,X2,…,Xn and an integer CC, we study the fundamental problem of computing the probability that the sum X=X1+X2+⋯+Xn is at most CC. We assume that each random variable XiXi is implicitly given by an oracle OiOi, which given two input integers n1,n2n1,n2 returns the probability of n1≤Xi≤n2n1≤Xi≤n2. We give the first deterministic fully polynomial-time approximation scheme (FPTAS) to estimate the probability up to a relative error of 1±ϵ1±ϵ. Our algorithm is based on the technique for approximately counting knapsack solutions, developed in Gopalan et al. (2011).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 42, Issue 3, May 2014, Pages 197–202
Journal: Operations Research Letters - Volume 42, Issue 3, May 2014, Pages 197–202
نویسندگان
Jian Li, Tianlin Shi,