کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141840 | 957095 | 2008 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The inverse 1-median problem on a cycle
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let the graph G=(V,E)G=(V,E) be a cycle with n+1n+1 vertices, non-negative vertex weights and positive edge lengths. The inverse 1-median problem on a cycle consists in changing the vertex weights at minimum cost so that a prespecified vertex becomes the 1-median. All cost coefficients for increasing or decreasing the weights are assumed to be 1. We show that this problem can be formulated as a linear program with bounded variables and a special structure of the constraint matrix: the columns of the linear program can be partitioned into two classes in which they are monotonically decreasing. This allows one to solve the problem in O(n2)O(n2) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 5, Issue 2, May 2008, Pages 242–253
Journal: Discrete Optimization - Volume 5, Issue 2, May 2008, Pages 242–253
نویسندگان
Rainer E. Burkard, Carmen Pleschiutschnig, Jianzhong Zhang,