کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1134374 956065 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A negative dual rectangle cancellation algorithm for the linear assignment problem
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مهندسی صنعتی و تولید
پیش نمایش صفحه اول مقاله
A negative dual rectangle cancellation algorithm for the linear assignment problem
چکیده انگلیسی
In this paper, we consider three alternative primal models and their corresponding alternative dual models for the linear assignment problem. We then define the concept of Negative Dual Rectangle (NDR) and suggest an algorithm that solves two of these dual problems by repeatedly finding and cancelling NDRs until it yields an optimal solution to the assignment problem. The algorithm is simple, flexible, efficient, and unified. We also introduce the notion of partial zero cover as an interpretation of an NDR. We then introduce some heuristic methods for finding NDRs. We also state and prove a lemma to establish the optimal use of an NDR. Furthermore, we show that on a new class of benchmark instances that is introduced in this paper the running time of our algorithm is highly superior to a well-known pure shortest path algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 65, Issue 4, August 2013, Pages 673-678
نویسندگان
, , ,