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

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
نویسندگان
, , ,