کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952513 | 1442040 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
ترجمه فارسی عنوان
یک روش تقریبی به طور کامل چندجملهای قطعی برای شمارش راه حلهای حلقوی صحیح آسان شده است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given n elements with nonnegative integer weights w=(w1,â¦,wn), an integer capacity C and positive integer ranges u=(u1,â¦,un), we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most C. We give a deterministic algorithm that estimates the number of solutions to within relative error ϵ in time polynomial in n, logâ¡U and 1/ϵ, where U=maxiâ¡ui. More precisely, our algorithm runs in O(n3log2â¡Uϵlogâ¡nlogâ¡Uϵ) time. This is an improvement of n2 and 1/ϵ (up to log terms) over the best known deterministic algorithm by Gopalan et al. (2011) [5]. Our algorithm is relatively simple, and its analysis is rather elementary. Our results are achieved by means of a careful formulation of the problem as a dynamic program, using the notion of binding constraints.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 645, 13 September 2016, Pages 41-47
Journal: Theoretical Computer Science - Volume 645, 13 September 2016, Pages 41-47
نویسندگان
Nir Halman,