Home  About us  Contact
 

Median Problem (median + problem)

Distribution by Scientific Domains
Mathematics and Statistics83%

Selected Abstracts

Exact optimal solutions of the minisum facility and transfer points location problems on a network

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2008
Mihiro Sasaki
Abstract We consider hierarchical facility location problems on a network called Multiple Location of Transfer Points (MLTP) and Facility and Transfer Points Location Problem (FTPLP), where q facilities and p transfer points are located and each customer goes to one of the facilities directly or via one of the transfer points. In FTPLP, we need to find an optimal location of both the facilities and the transfer points while the location of facilities is given in MLTP. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been tested due to the size of the problems. We show that the minisum MLTP can be formulated as a p -median problem, which leads to obtaining an optimal solution. We also present a new formulation of FTPLP and an enumeration-based approach to solve the problems with a single facility. [source]

Solution methods for the p -median problem: An annotated bibliography

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2006
J. Reese
Abstract The p -median problem is a network problem that was originally designed for, and has been extensively applied to, facility location. In this bibliography, we summarize the literature on solution methods for the uncapacitated and capacitated p -median problem on a network. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(3), 125,142 2006 [source]

An improved algorithm for the minmax regret median problem on a tree

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2003
Igor Averbakh
Abstract We consider the 1-median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a "minmax regret" location, that is, to minimize the worst-case loss in the objective function that may occur because the decision is made without knowing which state of nature will take place. For this problem on a tree, the best published algorithm has complexity O(n2). We present an algorithm with complexity O(n log2n). © 2003 Wiley Periodicals, Inc. [source]

Efficient algorithms for centers and medians in interval and circular-arc graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2002
Sergei Bespamyatnikh
Abstract The p -center problem is to locate p facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The p -median problem is to locate p facilities on a network so as to minimize the average distance from a demand point to its closest facility. We consider these problems when the network can be modeled by an interval or circular-arc graph whose edges have unit lengths. We provide, given the interval model of an n vertex interval graph, an O(n) time algorithm for the 1-median problem on the interval graph. We also show how to solve the p -median problem, for arbitrary p, on an interval graph in O(pn log n) time and on a circular-arc graph in O(pn2 log n) time. We introduce a spring representation of the objective function and show how to solve the p -center problem on a circular-arc graph in O(pn) time, assuming that the arc endpoints are sorted. © 2002 Wiley Periodicals, Inc. [source]

Exploiting self-canceling demand point aggregation error for some planar rectilinear median location problems

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 6 2003
R.L. Francis
When solving location problems in practice it is quite common to aggregate demand points into centroids. Solving a location problem with aggregated demand data is computationally easier, but the aggregation process introduces error. We develop theory and algorithms for certain types of centroid aggregations for rectilinear 1-median problems. The objective is to construct an aggregation that minimizes the maximum aggregation error. We focus on row-column aggregations, and make use of aggregation results for 1-median problems on the line to do aggregation for 1-median problems in the plane. The aggregations developed for the 1-median problem are then used to construct approximate n -median problems. We test the theory computationally on n -median problems (n , 1) using both randomly generated, as well as real, data. Every error measure we consider can be well approximated by some power function in the number of aggregate demand points. Each such function exhibits decreasing returns to scale. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 614,637, 2003. [source]