کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420278 683915 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Integer matrices with constraints on leading partial row and column sums
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Integer matrices with constraints on leading partial row and column sums
چکیده انگلیسی

Consider the problem of finding an integer matrix that satisfies given constraints on its leading partial row and column sums. For the case in which the specified constraints are merely bounds on each such sum, an integer linear programming formulation is shown to have a totally unimodular constraint matrix. This proves the polynomial-time solvability of this case. In another version of the problem, one seeks a zero–one matrix with prescribed row and column sums, subject to certain near-equality constraints, namely, that all leading partial row (respectively, column) sums up through a given column (respectively, row) are within unity of each other. This case admits a polynomial reduction to the preceding case, and an equivalent reformulation as a maximum-flow problem. The results are developed in a context that relates these two problems to consistent matrix rounding.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 16, 28 August 2010, Pages 1838–1847
نویسندگان
,