A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions

The single facility location problem with demand regions seeks for a facility location minimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. \(\ell _1\) or \(\ell _\infty \). We develop an exact combinatorial algorithm running in time \(O(n\log ^c n)\) for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.     

Sorting weighted distances with applications to objective function evaluations in single facility location problems

We consider single facility location problems defined on rectilinear spaces and spaces induced by tree networks. We focus on discrete cases, where the facility is restricted to be in a prespecified finite set S, and the goal is to evaluate the objective at each point in S. We present efficient improved algorithms to perform this task for several classes of objective functions.     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D₉, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).     

CE equivalence and shape equivalence of 1-dimensional compacta

In this paper the relationship between CE equivalence and shape equivalence for locally connected, 1-dimensional compacta is investigated. Two theorems are proved. The first asserts that every path connected planar continuum is CE equivalent either to a bouquet of circles or to the Hawaiian earring. The second asserts that for every locally connected, 1-dimensional continuum X there is a cell-like map of X onto a planar continuum. It follows that CE equivalence and shape equivalence are the same for the class of all locally connected, 1-dimensional compacta. In addition, an example of Ferry is generalized to show that for every n⩾1 there exists an n-dimensional, LCⁿ⁻² continuum Y such that Sh(Y)=Sh(S¹) but Y is not CE equivalent to S¹.     

A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems where Distances are Rectangular

The problem of locating new facilities with respect to existing facilities is stated as a linear programming problem where inter-facility distances are assumed to be rectangular. The criterion of location is the minimization of the maximum weighted rectangular distance in the system. Linear constraints which (a) limit the new facility locations and (b) enforce upper bounds on the distances between new and existing facilities and between new facilities can be included. The dual programming problem is formulated in order to provide for an efficient solution procedure. It is shown that the duLal variables provide information abouLt the complete range of new facility locations which satisfy the minimax criterion.     

Graph partitions with minimum degree constraints

Given a graph with n nodes and minimum degree δ, we give a polynomial time algorithm that constructs a partition of the nodes of the graph into two sets X and Y such that the sum of the minimum degrees in X and in Y is at least δ and the cardinalities of X and Y differ by at most δ(δ + 1 if n ≠ δ(mod2)). The existence of such a partition was shown by Sheehan (1988).     

A BSSS algorithm for the single facility location problem in two regions with different norms

Suppose the plane is divided by a straight line into two regions with different norms. We want to find the location of a single new facility such that the sum of the distances from the existing facilities to this point is minimized. This is in fact a non-convex optimization problem. The main difficulty is caused by finding the distances between points on different sides of the boundary line. In this paper we present a closed form solution for finding these distances. We also show that the optimal solution lies in the rectangular hull of the existing points. Based on these findings then, an efficient big square small square (BSSS) procedure is proposed.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

The Ordered Gradual Covering Location Problem on a Network

In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. The Ordered Median Location problem is a generalization of most of the classical locations problems like p-median or p-center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities is already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.     

Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

Multi-objective competitive location problem with distance-based attractiveness and its best non-dominated solution

The multi-objective competitive location problem (MOCLP) with distance-based attractiveness is introduced. There are m potential competitive facilities and n demand points on the same plane. All potential facilities can provide attractiveness to the demand point which the facility attractiveness is represented as distance-based coverage of a facility, which is “full coverage” within the maximum full coverage radius, “no coverage” outside the maximum partial coverage radius, and “partial coverage” between those two radii. Each demand point covered by one of m potential facilities is determined by the greatest accumulated attractiveness provided the selected facilities and least accumulated distances between each demand point and selected facility, simultaneously. The tradeoff of maximum accumulated attractiveness and minimum accumulated distances is represented as a multi-objective optimization model. A proposed solution procedure to find the best non-dominated solution set for MOCLP is introduced. Several numerical examples and instances comparing with introduced and exhaustive method demonstrates the good performance and efficiency for the proposed solution procedure.     

Computing a maxian point of a simple rectilinear polygon

Let P be a simple rectilinear polygon with n vertices. There are k points in P. The maxian problem is to locate a single facility in P so as to maximize the sum of its distance from it to the k points. We present an O((n×k)logn) time algorithm for this problem.     

On the dependence between the extreme order statistics in the proportional hazards model

Let X₁,…,X_n be a random sample from an absolutely continuous distribution with non-negative support, and let Y₁,…,Y_n be mutually independent lifetimes with proportional hazard rates. Let also X₍₁₎<?<X_(n) and Y₍₁₎<?<Y_(n) be their associated order statistics. It is shown that the pair (X₍₁₎,X_(n)) is then more dependent than the pair (Y₍₁₎,Y_(n)), in the sense of the right-tail increasing ordering of Avérous and Dortet-Bernadet [LTD and RTI dependence orderings, Canad. J. Statist. 28 (2000) 151-157]. Elementary consequences of this fact are highlighted.     

Finite graphs have unique symmetric products

Let X be a metric continuum and let Fn(X) be the nth symmetric product of X (Fn(X) is the hyperspace of nonempty subsets of X with at most n points). In this paper we prove that if Fn(X) is homeomorphic to Fn(Y), where X is a finite graph and Y is a continuum, then X is homeomorphic to Y.     

A generalized Weiszfeld method for the multi-facility location problem

An iterative method is proposed for the K facilities location problem. The problem is relaxed using probabilistic assignments, depending on the distances to the facilities. The probabilities, that decompose the problem into K single-facility location problems, are updated at each iteration together with the facility locations. The proposed method is a natural generalization of the Weiszfeld method to several facilities.     

Limiting distributions of functionals of Markov chains

Let \s{X_n, n ? 0\s} and \s{Y_n, n ? 0\s} be two stochastic processes such that Y_n depends on X_n in a stationary manner, i.e. P(Y_n ? A\vbX_n) does not depend on n. Sufficient conditions are derived for Y_n to have a limiting distribution. If X_n is a Markov chain with stationary transition probabilities and Y_n = f(X_n,..., X_n+k) then Y_n depends on X_n is a stationary way. Two situations are considered: (i) \s{X_n, n ? 0\s} has a limiting distribution (ii) \s{X_n, n ? 0\s} does not have a limiting distribution and exits every finite set with probability 1. Several examples are considered including that of a non-homogeneous Poisson process with periodic rate function where we obtain the limiting distribution of the interevent times.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

Systems of sets such that each set properly intersects at most one other set—Application to cluster analysis

A set X is said to properly intersect a set Y if none of the sets X∩Y, X?Y and Y?X is empty. In this paper, we consider collections of subsets such that each member of the collection properly intersects at most one other member. Such collections are hereafter called paired hierarchical collections. The two following combinatorial properties are investigated. First, any paired hierarchical collection is a set of intervals of at least one linear order defined on the ground set. Next, the maximum size of a paired hierarchical collection defined on an n-element set is . The properties of these collections are also investigated from the cluster analysis point of view. In the framework of the general bijection defined by Batbedat [Les isomorphismes HTS et HTE (après la bijection de Benzécri-Johnson), Metron 46 (1988) 47-59] and Bertrand [Set systems and dissimilarities, European J. Combin. 21 (2000) 727-743], we characterize the dissimilarities that are induced by weakly indexed paired hierarchical collections. Finally, we propose a proof of the so-called agglomerative paired hierarchical clustering (APHC) algorithm that extends the well-known AHC algorithm in order to allow that some clusters can be merged twice. An implementation and some illustrations of this algorithm and of a variant of it were presented by Chelcea et al. [A new agglomerative 2-3 hierarchical clustering algorithm, in: D. Baier, K.-D. Wernecke (Eds.), Innovations in Classification, Data Science, and Information Systems (GfKL 2003), Springer, Berlin, 2004, pp. 3-10 and Un Nouvel Algorithme de Classification Ascendante 2-3 Hiérarchique, in: Reconnaissance des Formes et Intelligence Artificielle (RFIA 2004), vol. 3, Toulouse, France, 2004, pp. 1471-1480. Available at 〈http://www.laas.fr/rfia2004/actes/ARTICLES/388.pdf〉].