We consider the single-facility ordered median location problem with uncertainty in the parameters (weights) defining the objective function. We study two cases. In the first case, the uncertain weights belong to a region with a finite number of extreme points, and in the second case, they must satisfy some order constraints and belong to some box (convex case). To deal with the uncertainty, we apply the minimax regret approach, providing strongly polynomial time algorithms to solve these problems. Finally, we also extend the proposed methodology to other problems with order constraints, which are not necessarily convex.

Abstract We consider a generalization of the median and center facility location problem called the collection depots facility location (CDFL) problem. We are given a set of client locations and a set of collection depots and we are required to find the placement for a certain number of facilities, so that the cost of dispatching a vehicle from a facility, to a client, to a collection depot, and back, is optimized for all clients. The CDFL center problem minimizes the cost of the most expensive vehicle tour among all clients, and the CDFL median problem minimizes the sum of the tour costs for all clients. We provide the first polynomial time algorithms to solve the 1 and k median problems in trees with time complexities O(n log n) and O(kn3), respectively, where n is the number of vertices in the tree. In contrast, a restricted version of the k‐median problem, where clients are given lists of allowed collection depots, is NP‐complete even for star graphs. We also give an optimal linear time algorithm to solve the discrete and continuous weighted 1‐center problem, improving on the O(n log n) result of Tamir and Halman [Discrete Optimization 2(2005), 168–184]. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract We examine a class of problems that seeks to find tree‐structured networks that minimize the maximum cost among a subset of nodes in a graph. The cost metric is characterized by a series of parameters that can represent distance, flow volume, and delivery deadlines. Derived through variations in problem parameters, we present 17 different problems and discuss their worst‐case complexities. Fourteen of the problems are new to the literature. We show that some of the problems are 𝒩𝒫‐Complete and others are polynomially solvable. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract Given a tree network T with n nodes, let 𝒫L be the subset of all discrete paths whose length is bounded above by a prespecified value L. We consider the location of a path‐shaped facility P ∈ 𝒫L, where customers are represented by the nodes of the tree. We use a bi‐criteria model to represent the total transportation cost of the customers to the facility. Each node is associated with a pair of nonnegative weights: the center‐weight and the median‐weight. In this doubly weighted model, a path P is assigned a pair of values (MAX(P),SUM(P)), which are, respectively, the maximum center‐weighted distance and the sum of the median‐weighted distances from P to the nodes of the tree. Viewing 𝒫L and the planar set {(MAX(P),SUM(P)) : P ∈ 𝒫L} as the decision space and the bi‐criteria or outcome space respectively, we focus on finding all the nondominated points of the bi‐criteria space. We prove that there are at most 2n nondominated outcomes, even though the total number of efficient paths can be Ω(n2), and they can all be generated in O(n log n) optimal time. We apply this result to solve the cent‐dian model, whose objective is a convex combination of the weighted center and weighted median functions. We also solve the restricted models, where the goal is to minimize one of the two functions MAX or SUM, subject to an upper bound on the other one, both with and without a constraint on the length of the path. All these problems are solved in linear time, once the set of nondominated outcomes has been obtained, which in turn, results in an overall complexity of O(n log n). The latter bounds improve upon the best known results by a factor of O(log n). © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 237–247 2006

Abstract In a recent article Averbakh and Berman present an O(p3 + n2) serial algorithm to solve the distance constrained p‐center location problem with mutual communication on a tree network with n nodes. In this note we suggest two simple modifications leading to the improved (subquadratic in n), O(p3 + p(n + p)log2(n + p)) complexity bound. We also present a new O(p2n log n log(n + p)) algorithm for the discrete version of this problem. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 38–40 2004

We consider the traveling salesman problem when the cities are points in ℝ d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral norm, the problem of finding a tour of maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O ( n f -2 log n ), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus, for example, we have O ( n 2 log n ) algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a minimum length tour in each case is NP-hard. Our approach can be extended to the more general case of quasi-norms with a not necessarily symmetric unit ball, where we get a complexity of O ( n 2 f -2 log n ).For the special case of two-dimensional metrics with f = 4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O ( n ) running time. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Ω( n log n ) time. The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms.Complementing the results on simplicity for polyhedral norms, we prove that, for the case of Euclidean distances in ℝ d for d ≥ 3, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.

Abstract We consider a rather large class of p‐facility location models including the p‐median, p‐center, and other related and more general models. For any such model of interest with p new facilities, let v(p) denote the minimal objective function value and let n be the number of demand points. Given 1 ≤ p < q ≤ n, we find easily computed positive constants k(p, q), where v(q)/v(p) ≤ k(p, q) ≤ 1. These resulting inequalities relating v(p) and v(q) are worst case, since they are attained as equalities for a class of “hub‐and‐spoke” trees. Our results also provide insight into some demand point aggregation problems, where a graph of the function v(q) can provide an upper bound on aggregation error. © 2002 Wiley Periodicals, Inc.

The most common problems studied in network location theory are the p-median and the p-center models. The p-median problem on a network is concerned with the location of p points (medians) on the network, such that the total (weighted) distance of all the nodes to their respective nearest points is minimized. The p-center problem is concerned with the location of p-points (centers) on the network, such that the maximum (weighted) distance of all the nodes to their respective nearest points is minimized. To capture more real-world problems and obtain a good way to trade-off minisum (efficiency) and minimax (equity) approaches, Halpern introduced the centdian model, where the objective is to minimize a convex combination of the objective functions of the center and the median problems. In this paper, we studied the p-centdian problem on tree networks and present the first polynomial time algorithm for this problem. © 1998 John Wiley & Sons, Inc. Networks 32:255–262, 1998

This paper considers the problem of locating a central facility on a tree network. The central facility takes the form of a subtree of the network and provides service to several demand points located at the nodes of the network. Two types of costs are involved in evaluating a given facility selection. The setup cost represents the costs of establishing the facility and is taken to be directly proportional to the total length of the facility. The transportation cost is the cost associated with the travel of customers to the central facility. The objective function is to select a tree-shaped facility that will minimize the sum of the setup cost and the total transportation cost. We introduce a general model and a simple “bottom-up” dynamic programming algorithm for its solution. We then focus on the important class of covering problems, where the transportation cost of a customer to the serving facility is zero if the distance between the two is below a certain threshold and it is equal to some penalty term otherwise. We improve upon the performance of existing methods, and present algorithms with subquadratic complexity. © 1996 John Wiley & Sons, Inc.

Abstract We consider the problem of locating new facilities with respect to existing facilities on a tree network. The objective is to minimize the maximum of the weighted distances between existing and new facilities and between pairs of new facilities. There are upper bounds on the distances between pairs of new facilities and between new and existing facilities. We give a polynomial order, binary search algorithm, based on rational representation of data. We also present a strongly polynomial order algorithm employing a parameteric approach and exploiting parallelism.

Abstract Minieka and Hakimi et al. considered the problem of locating a tree‐shaped facility of a given length in a tree network, with the objective of maximizing the sum of node distances from this facility. They stated the complexity of the model as an open problem. We prove that it is NP‐complete and provide a pseudopolynomial time algorithm.

Abstract In two recent papers, similar multifacility problems on tree networks were studied where facilities are subtrees of the tree. The complexity of the problems was left as open. In this paper, we formulate a general model that includes the above‐cited problems as special cases and give a polynomial algorithm to solve the general model.

This paper discusses new complexity results for several models dealing with the location of obnoxious or undesirable facilities on graphs. The focus is mainly on the continuous p-Maximin and p-Maxisum dispersion models, where the facilities can be established at the nodes or in the interiors of the edges. For the general (nonhomogeneous) case it is shown that both models are strongly NP-hard even when the underlying graph consists of a single edge. For the homogeneous p-Maximin model it is proven that even the problem of finding a $\frac{2}{3}$-approximation solution is NP-hard, and a polynomial heuristic which provides a $\frac{1}{2}$-approximation to the model is presented. Tree graphs are considered, and new algorithms with lower complexity bounds for several versions of the model are presented. For the p-Maxisum problem we show that the homogeneous case is NP-hard on general graphs. Turning to the homogeneous case on trees, a certain concavity property is identified and then utilized to improve upon the best known methods to solve this model.

Abstract In many services (e.g., delivery, or customer pickup vehicles) the service unit usually visits a number of demand points on a single multistop tour. Typically, at a specific time of the day, the unit receives the list of waiting calls and immediately starts a tour of the network that includes all waiting customers. The multistop location problem is to find the home location for the service unit. We focus on the minimax criterion for the multistop problem defined on a tree network. Each potential list of customers is associated with the length of its respective tour and with some weight. We seek for the home location of the unit that minimizes the maximum weighted tour length over all feasible customer lists. We consider several weight functions and obtain results that reveal additional properties of the classical absolute center of the tree.

Several center location problems on general networks and even on tree networks are nonconvex. Known solution procedures are based on decomposing the problem into subproblems, finding each one of the local solutions independently, and then selecting among them the best solution. The purpose of this paper is to demonstrate that for some location models, it is possible to take advantage and use information that is common to certain subproblems in order to obtain better complexity bounds. The main tool implemented is a dynamic data structure that is used to maintain the objective (dynamically) as we move from one subproblem to the next. This study focuses on (nonconvex) obnoxious center location problems on trees, and on the classical p-center problem on general networks. In both cases better complexity bounds are derived.

An $O(n\log ^3 n)$ algorithm for the continuous p-center problem on a tree is presented. Following a sequence of previous algorithms, ours is the first one whose time bound in uniform in p and less than quadratic in n. We also present an $O(n\log ^2 n\log \log n)$ algorithm for a weighted discrete p-center problem.

Many known algorithms are based on selection in a set whose cardinality is superlinear in terms of the input length. It is desirable in these cases to have selection algorithms that run in sublinear time in terms of the cardinality of the set. This paper presents a successful development in this direction. The methods developed here are applied to improve the previously known upper bounds for the time complexity of various location problems.

The following class of matching problems is considered. The vertices of a complete undirected graph are indexed $1, \cdots ,n$, where $n = 2m$. Every vertex i is assigned two numbers $a_i $, $b_i $. The length of every edge $(i,j)$, where $i < j$, is $d(i,j) = a_i + b_j $. This class of weighted graphs is applicable to scheduling and optimal assignment problems. A maximum weighted (perfect) matching is found in $O(n \cdot \log n)$ operations.