کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872490 | 681651 | 2014 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterization of facets of the hop constrained chain polytope via dynamic programming
ترجمه فارسی عنوان
خصوصیات جنبه های چند ضلعی زنجیره ای محدود شده توسط برنامه های پویا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محدودیت هاپ، زنجیر، برنامه نویسی دینامیک، چهره ها،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result in characterizations of all facet defining 0/±1-inequalities for the hop constrained chain polytope and all facet defining 0/1-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper by Dahl and Gouveia in 2004.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 229-246
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 229-246
نویسندگان
Martin Grötschel, Rüdiger Stephan,