کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651332 1632450 2006 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edmonds polytopes and a hierarchy of combinatorial problems
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Edmonds polytopes and a hierarchy of combinatorial problems
چکیده انگلیسی

Let S be a set of linear inequalities that determine a bounded polyhedron P. The closure of S is the smallest set of inequalities that contains S   and is closed under two operations: (i) taking linear combinations of inequalities, (ii) replacing an inequality Σajxj≤a0Σajxj≤a0, where a1,a2,…,ana1,a2,…,an are integers, by the inequality Σajxj≤aΣajxj≤a with a≥[a0]a≥[a0]. Obviously, if integers x1,x2,…,xnx1,x2,…,xn satisfy all the inequalities in S, then they satisfy also all inequalities in the closure of S  . Conversely, let Σcjxj≤c0Σcjxj≤c0 hold for all choices of integers x1,x2,…,xnx1,x2,…,xn, that satisfy all the inequalities in S  . Then we prove that Σcjxj≤c0Σcjxj≤c0 belongs to the closure of S. To each integer linear programming problem, we assign a nonnegative integer, called its rank. (The rank is the minimum number of iterations of the operation (ii) that are required in order to eliminate the integrality constraint.) We prove that there is no upper bound on the rank of problems arising from the search for largest independent sets in graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 10–11, 28 May 2006, Pages 886–904
نویسندگان
,