We study a non-cooperative multi-player game of rational customers in a queueing network composed of two unobservable single-server subsystems with different regimes. The first subsystem is a free-shared first-come first-served queue with waiting time affected by congestion. Wishing to avoid congestion, customers may choose to turn to the second subsystem that offers service with no delay. However, reaching the second server is costly and can go unrewarded because requests are blocked when the server is busy. Still, blocked customers do not leave the system empty-handed-they are instantaneously rerouted to the shared queue at the first server. The decision and benefit of each customer depend on the choices of the others, bringing about a symmetric non-cooperative game. After analyzing the queueing characteristics of the system, we show, by properties of the cost function, that a unique symmetric Nash equilibrium exists. Comparing the equilibrium strategy with the socially optimal strategy, we find that, contrary to intuition, customers may choose the loss system more, less or in an equal proportion to what is socially preferred.

We suggest a novel approach to model continuous time processes of the interactions of independent elements. The model assumes a finite number of independent Markov chains, each representing an element. Chains move among a common space of states. Sometimes chains intersect, being in the same state at the same time. These intersections relate the chains with each other and imply many interesting processes. In this paper, we examine our new approach in the context of network evolution. Our analytic study achieves a closed solution for the expected time until a node has any specific degree. Our numerical study demonstrates properties which are in agreement with real world networks. Thus we show the potential of our approach. (C) 2016 Elsevier B.V. All rights reserved.

We consider a loss system with a fixed budget for servers. The system owner's problem is choosing the price, and selecting the number and quality of the servers, in order to maximize profits, subject to a budget constraint. We solve the problem with identical and different service rates as well as with preemptive and nonpreemptive policies. In addition, when the policy is preemptive, we prove the following conservation law: the distribution of the total service time for a customer entering the slowest server is hyperexponential with expectation equal to the average service rate independent of the allocation of the capacity. (c) 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 81-97, 2015

Consider a non-preemptive M/M/1 system with two first-come first-served queues, virtual (VQ) and system (SQ). An arriving customer who finds the server busy decides which queue to join. Customers in the SQ have non-preemptive priority over those in the VQ, but waiting in the SQ is more costly. We study two information models of the system. In the unobservable model, customers are notified only whether the server is busy, and in the observable model they are also informed about the number of customers currently waiting in the SQ. We characterize the Nash equilibrium of joining strategies in the two models and demonstrate a surprising similarity of the solutions.

We study the problem of locating facilities on the nodes of a network to maximize the expected demand serviced. The edges of the input graph are subject to random failure due to a disruptive event. We consider a special type of failure correlation. The edge dependency model assumes that the failure of a more reliable edge implies the failure of all less reliable ones. Under this dependency model called Linear Reliability Order (LRO) we give two polynomial time exact algorithms. When two distinct LRO's exist, we prove the total unimodularity of a linear programming formulation. In addition, we show that minimizing the sum of facility opening costs and expected cost of unserviced demand under two orderings reduces to a matching problem. We prove NP-hardness of the three orderings case and show that the problem with an arbitrary number of orderings generalizes the deterministic maximum coverage problem. When a demand point can be covered only if a facility exists within a distance limit, we show that the problem is NP-hard even for a single ordering.

We consider Stackelberg pricing games between two servers with homogeneous customers. We find that a first-mover advantage holds when the demand is large and that a second-mover advantage exists when the demand is scarce. (C) 2013 Elsevier B.V. All rights reserved.

Let G be a complete (undirected) graph with 31 vertices. Given a binary weight function on the edges of G, the BINARY MAXIMUM 2-PATH PARTITIONING PROBLEM is to compute a set of l vertex-disjoint simple 2-edge paths with maximum total edge weight. The problem is NP-hard (Garey and Johnson 1979) [1]. In this paper we propose a simple local search algorithm with polynomial running time for the problem and analyze its performance for several search depths. For depth 2, we show that the algorithm is a 0.3333-approximation, and that the bound is tight. For depth 3, we show that the algorithm is a 0.4-approximation. For depth 9, we show that the algorithm is a 0.55-approximation, improving on the best-known 0.5265 bound for the problem. We also consider the special case where G is subcubic, that is, the maximum degree in its subgraph induced by the unit-weight edges is 3. In this case we show that the algorithm is a 0.375-approximation for depth 2 and a 0.5-approximation for depth 3. In addition, we show that depth 7 is sufficient for the 0.55 bound guarantee. Finally we give, by means of bad instances, upper bounds on the performance guarantees of the algorithm. For depth 2 we show a 0.4 upper bound in the subcubic case. For depth 3 we show a 0.6 upper bound, as well as a 0.7 upper bound in the subcubic case. For the general (non-negative) weight problem we show a 0.5556 upper bound for depth 3 (for depth 2, the tight 0.3333 ratio holds for this problem as well). (C) 2013 Elsevier B.V. All rights reserved.

Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of C. The cycle-radius of H is similarly defined except that cycles are replaced by directed closed walks. We prove that there exists for every nonnegative edge weight function an orientation H of G whose cycle-radius equals that of G if and only if G is series-parallel. (C) 2011 Elsevier B.V. All rights reserved.

Arkin, Esther M.
Guttmann-Beck, Nili
Hassin, Refael

This paper considers a generalization of the capacitated spanning tree problem, in which some of the vertices have capacity K, and the others have capacity k < K. We prove that the problem can be approximated within a constant factor, and present better approximations when k is 1 or 2. (C) 2012 Elsevier B.V. All rights reserved.

Given a complete graph G = (V E), a weight function w : E -> N(0) on its edges, and p -> N(0) a penalty function on its vertices, the PENALIZED k-MIN-SUM PROBLEM is the problem of finding a partition of V to k + 1 sets, S(1),...,S(k+1), minimizing Sigma(k)(i=1)w(S(i)) + p(S(k+1)), where for S subset of V w(S) = E(e=(ij) subset of S)w(e), and p(S) = Sigma(i is an element of S)p(i). Our main result is a randomized approximation scheme for the metric version of the penalized 1-min-sum problem, when the ratio between the minimal and maximal penalty is bounded. For the metric penalized k-min-sum problem where k is a constant, we offer a 2-approximation. (C) 2010 Elsevier B.V. All rights reserved.