کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141746 957088 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The dominance assignment problem
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
The dominance assignment problem
چکیده انگلیسی

We prove the following remarkable fact for matrices with entries from an ordered set: For any m×nm×n matrix AA and a given integer h≤min{m,n}h≤min{m,n} there exists a matrix C=(cij)C=(cij), obtained from AA by permuting its rows and columns, such that cm−h+i,i≤cjkcm−h+i,i≤cjk for j≤m−h+ij≤m−h+i and i≤ki≤k. Moreover, we give a polynomial algorithm to transform AA into CC. We also prove that when h=m=nh=m=n and all entries of AA are distinct, the diagonal of CC solves the lexicographic bottleneck assignment problem, and that the given algorithm has complexity O(n3n/logn), which is the best performance known for this kind of matrices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 9, Issue 3, August 2012, Pages 149–158
نویسندگان
, ,