کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950810 | 1441036 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity and approximability of budget-constrained minimum cost flows
ترجمه فارسی عنوان
در مورد پیچیدگی و تقریبی بودن محدودیت های حداقل هزینه جریان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ها، پیچیدگی، حداقل هزینه جریان، نزدیک شدن
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We investigate the complexity and approximability of the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a second kind of costs associated with each arc, whose total value in a feasible flow is constrained by a given budget B. This problem appears both in practical applications and as a subproblem when applying the ε-constraint method to the bicriteria minimum cost flow problem. We show that we can solve the problem exactly in weakly polynomial time O(logâ¡Mâ
MCF(m,n,C,U)), where C, U, and M are upper bounds on the largest absolute cost, largest capacity, and largest absolute value of any number occurring in the input, respectively, and MCF(m,n,C,U) denotes the complexity of finding a traditional minimum cost flow. Moreover, we present two fully polynomial-time approximation schemes for the problem on general graphs and one with an improved running-time for the problem on acyclic graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 126, October 2017, Pages 24-29
Journal: Information Processing Letters - Volume 126, October 2017, Pages 24-29
نویسندگان
Michael Holzhauser, Sven O. Krumke, Clemens Thielen,