A new algorithm to solve the minimum cost flow problem
محل انتشار: نهمین کنفرانس بین المللی مهندسی صنایع
سال انتشار: 1391
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 1,531
فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
IIEC09_066
تاریخ نمایه سازی: 26 اسفند 1391
چکیده مقاله:
In this paper, we present a new approach to solve the minimum cost flow problem using the out-of-kilter idea. Our algorithm uses Minty's Lemma to transform all the out-of-kilterarcs into in-kilter arcs. This algorithm gives a geometrical explanation to the optimality concept. For a network with nnodes and m arcs, the algorithm performs O(log(nU)) phases and runs in O(m(m+n log n)log (nU)) time (where U is the largest absolute arc bound ), which is O(m(m+n log n) log n) under thesimilarity assumption[1]. This time is the running time of the algorithm in [2] which is the best strongly polynomial-time algorithms to solve this problem.
کلیدواژه ها:
نویسندگان
Mehdi Ghiyasvand
Bu-Ali Sina University