کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142025 | 1378600 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the tightness of an LP relaxation for rational optimization and its applications
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the tightness of an LP relaxation for rational optimization and its applications On the tightness of an LP relaxation for rational optimization and its applications](/preview/png/1142025.png)
چکیده انگلیسی
We consider the problem of optimizing a linear rational function subject to totally unimodular (TU) constraints over {0,1} variables. Such formulations arise in many applications including assortment optimization. We show that a natural extended LP relaxation of the problem is “tight”. In other words, any extreme point corresponds to an integral solution. We also consider more general constraints that are not TU but obtained by adding an arbitrary constraint to the set of TU constraints. Using structural insights about extreme points, we present a polynomial time approximation scheme (PTAS) for the general problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 44, Issue 5, September 2016, Pages 612-617
Journal: Operations Research Letters - Volume 44, Issue 5, September 2016, Pages 612-617
نویسندگان
Vashist Avadhanula, Jalaj Bhandari, Vineet Goyal, Assaf Zeevi,