Abstract In this article, we study the complexity of the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem is NP‐hard on general networks. However, in some particular cases, we prove that this problem is solvable in polynomial time. The cases of star and path networks combined with different assumptions for the model parameters are analysed. In particular, we obtain that the problem on star networks is solvable in time for uniform weights and NP‐hard for non‐uniform weights. On paths, the single facility problem is solvable in time, while the ‐facility problem is NP‐hard even with uniform costs and upper bounds (maximal upgrading per edge), as well as, integer parameter values. Furthermore, a pseudo‐polynomial algorithm is developed for the single facility problem on trees with integer parameters.

Abstract A new framework for portfolio diversification is introduced which goes beyond the classical mean-variance approach and portfolio allocation strategies such as risk parity. It is based on a novel concept called portfolio dimensionality that connects diversification to the non-Gaussianity of portfolio returns and can typically be defined in terms of the ratio of risk measures which are homogenous functions of equal degree. The latter arises naturally due to our requirement that diversification measures should be leverage invariant. We introduce this new framework and argue the benefits relative to existing measures of diversification in the literature, before addressing the question of optimizing diversification or, equivalently, dimensionality. Maximising portfolio dimensionality leads to highly non-trivial optimization problems with objective functions which are typically non-convex and potentially have multiple local optima. Two complementary global optimization algorithms are thus presented. For problems of moderate size and more akin to asset allocation problems, a deterministic Branch and Bound algorithm is developed, whereas for problems of larger size a stochastic global optimization algorithm based on Gradient Langevin Dynamics is given. We demonstrate analytically and through numerical experiments that the framework reflects the desired properties often discussed in the literature.

We consider 2‐facility location problems with equity measures, defined on networks. The models discussed are, the variance, the mean of absolute weighted deviations, the maximum weighted absolute deviation, the sum of absolute weighted differences, and the range. We give new algorithmic results for these models in the 2‐facility case. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 1–9. 2015

This paper proposes a heuristic for districting problems arising in an arc routing context. The aim is to design districts by amalgamating edges of a graph as opposed to cells. Solutions must satisfy two hard criteria (complete and exclusive assignment as well as connectedness) and several soft criteria (balance, small deadheading, local compactness, and global compactness). The latter criteria are amalgamated into a weighted objective. The proposed heuristic applies a construction procedure followed by a tabu search improvement phase in which several subroutines are defined and selected according to a roulette wheel mechanism, as in adaptive large neighborhood search. Extensive tests conducted on instances derived from real-world street data confirm the efficiency of the proposed methodology.

In this article, we consider the cooperative maximum covering location problem on a network. In this model, it is assumed that each facility emits a certain “signal” whose strength decays over distance according to some “signal strength function.” A demand point is covered if the total signal transmitted from all the facilities exceeds a predefined threshold. The problem is to locate facilities so as to maximize the total demand covered. For the 2‐facility problem, we present efficient polynomial algorithms for the cases of linear and piecewise linear signal strength functions. For the p‐facility problem, we develop a finite dominant set, a mixed‐integer programming formulation that can be used for small instances, and two heuristics that can be used for large instances. The heuristics use the exact algorithm for the 2‐facility case. We report results of computational experiments. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 334–349 2014

Abstract In this paper, we address the ordered p‐median problem, which includes as special cases most of the classical multifacility location problems discussed in the literature. Finite dominating sets (FDS) are known for particular instances of this problem: p‐median, p‐center, and p‐centdian. We find an FDS for the ordered p‐median problem. This set allows us to gain a better insight into the general FDS structure of network location problems. This FDS is later used to present the first polynomial time algorithm for p‐facility ordered median problems on tree networks. This result is combined with some approximation algorithms to give an O(log M log log M) approximate solution of these problems on general networks, where M is the number of vertices. © 2002 Wiley Periodicals, Inc.