کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421362 | 684206 | 2008 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Generating all minimal integral solutions to AND–OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Generating all minimal integral solutions to AND–OR systems of monotone inequalities: Conjunctions are simpler than disjunctions Generating all minimal integral solutions to AND–OR systems of monotone inequalities: Conjunctions are simpler than disjunctions](/preview/png/421362.png)
چکیده انگلیسی
We consider monotone ∨,∧∨,∧-formulae φφ of mm atoms, each of which is a monotone inequality of the form fi(x)⩾tifi(x)⩾ti over the integers, where for i=1,…,mi=1,…,m, fi:Zn↦Rfi:Zn↦R is a given monotone function and titi is a given threshold. We show that if the ∨∨-degree of φφ is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying φφ can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of mm inequalities is NP-hard when mm is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 11, 6 June 2008, Pages 2020–2034
Journal: Discrete Applied Mathematics - Volume 156, Issue 11, 6 June 2008, Pages 2020–2034
نویسندگان
Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich,