کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418512 681678 2016 30 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Core-based criterion for extreme supermodular functions
ترجمه فارسی عنوان
معیار مبتنی بر هسته برای توابع افراطی سوپرمودولار
کلمات کلیدی
عملکرد سوپرمودولار؛ عملکرد زیرمدولار ؛ هسته؛ استقلال مشروعیت؛ permutohedron تعمیم؛ چندسقفی Indecomposable
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We give a necessary and sufficient condition for extremality of a supermodular function based on its min-representation by means of (vertices of) the corresponding core polytope. The condition leads to solving a certain simple linear equation system determined by the combinatorial core structure. This result allows us to characterize indecomposability in the class of generalized permutohedra. We provide an in-depth comparison between our result and the description of extremality in the supermodular/submodular cone achieved by other researchers.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 206, 19 June 2016, Pages 122–151
نویسندگان
, ,