کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959667 | 1445955 | 2017 | 38 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reference points and approximation algorithms in multicriteria discrete optimization
ترجمه فارسی عنوان
نقاط مرجع و الگوریتم های تقریبی در بهینه سازی گسسته چند متغیری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی چندین متغیر، الگوریتم های تقریبی، روش های نقطه مرجع سازگاری برنامه نویسی، بهینه سازی ترکیبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We study the connection between reference point methods and approximation algorithms for multicriteria optimization problems over discrete sets. In particular, we establish that, in terms of computational complexity, computing approximate reference point solutions is polynomially equivalent to approximating the Pareto set. Complementing these results, we show for a number of general algorithmic techniques in single criteria optimization how they can be lifted to reference point optimization. In particular, we lift the link between dynamic programming and FPTAS, as well as certain LP-rounding techniques. The latter applies, e.g., to Set Cover and several machine scheduling problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 260, Issue 3, 1 August 2017, Pages 829-840
Journal: European Journal of Operational Research - Volume 260, Issue 3, 1 August 2017, Pages 829-840
نویسندگان
Christina Büsing, Kai-Simon Goetzmann, Jannik Matuschke, Sebastian Stiller,