کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952310 1442030 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximability issues for unconstrained and constrained maximization of half-product related functions
ترجمه فارسی عنوان
مسائل تقریبی برای حداکثر محدود کردن و محدود کردن توابع مربوط به نیمه محصول
کلمات کلیدی
ترجمه چکیده
ما با مشکل برنامه نویسی بولین به حداکثر رساندن تابع نیمه محصول، با و بدون محدودیت کوله پشتی خطی صحبت می کنیم. حداکثر کردن نیمه محصول را می توان در زمان چندجملهای انجام داد. اضافه کردن یک محدودیت کوله پشتی باعث می شود که مشکل در یک عامل ثابت نباشد، در صورتی که ضرایب در بخش خطی تابع منفی باشند. برای به حداکثر رساندن یک تابع با ضرایب مثبت در بخش خطی، یک طرح تقریبی به طور کامل چندجمله ای ایجاد می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
مسائل تقریبی برای حداکثر محدود کردن و محدود کردن توابع مربوط به نیمه محصول
چکیده انگلیسی
We address the Boolean programming problem of maximizing a half-product function, with and without a linear knapsack constraint. Maximizing the half-product can be done in polynomial time. Adding a knapsack constraint makes the problem non-approximable within a constant factor, provided that the coefficients in the linear part of the function are negative. For maximizing a function with positive coefficients in the linear part we develop a fully polynomial-time approximation scheme.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 659, 10 January 2017, Pages 64-71
نویسندگان
, , ,