A distance constrainedp-facility location problem on the real line

LetV = {v ₁,, v _n } be a set ofn points on the real line (existing facilities). The problem considered is to locatep new point facilities,F ₁,, F _p , inV while satisfying distance constraints between pairs of existing and new facilities and between pairs of new facilities. Fori = 1, , p, j = 1, , n, the cost of locatingF _i at pointv _j isc _ij . The objective is to minimize the total cost of setting up the new facilities. We present anO(p ³ n ² logn) algorithm to solve the model.     

Optimal Control of an M/G/1/K Queueing System with Combined <Emphasis Type="Italic">F</Emphasis> Policy and Startup Time

We investigate the optimal management problem of an M/G/1/K queueing system with combined F policy and an exponential startup time. The F policy queueing problem investigates the most common issue of controlling the arrival to a queueing system. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in the system. The method is illustrated analytically for exponential service time distribution. A cost model is established to determine the optimal management F policy at minimum cost. We use an efficient Maple computer program to calculate the optimal value of F and some system performance measures. Sensitivity analysis is also investigated.     

On the ( r | X p )-Medianoid Problem on a Network with Vertex and Edge Demands

This article considers the (r|X _p )-medianoid problem on a network N=(V,E) with vertex and edge demands. There are already p facilities located on the network and customers patronize the closest facility. The aim is to locate r additional facilities on the network where their captured demands will be maximized. Relationships with the (r|X _p )-medianoid problem with vertex demands are established. Complexity and algorithmic results are presented.     

The gravity p-median model

In this paper we propose a new model for the p-median problem. In the standard p-median problem it is assumed that each demand point is served by the closest facility. In many situations (for example, when demand points are communities of customers and each customer makes his own selection of the facility) demand is divided among the facilities. Each customer selects a facility which is not necessarily the closest one. In the gravity p-median problem it is assumed that customers divide their patronage among the facilities with the probability that a customer patronizes a facility being proportional to the attractiveness of that facility and to a decreasing utility function of the distance to the facility.     

Optimal location with equitable loads

The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn ³) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.     

Cooperative Parallel Variable Neighborhood Search for the p-Median

We propose a cooperative multi-search method for the Variable Neighborhood Search (VNS) meta-heuristic based on the central-memory mechanism that has been successfully applied to a number of difficult combinatorial problems. In this approach, several independent VNS meta-heuristics cooperate by asynchronously exchanging information about the best solutions identified so far, thus conserving the simplicity of the original, sequential VNS ideas. The p-median problem (PM) serves as test case. Extensive experimentations have been conducted on the classical TSPLIB benchmark problem instances with up to 11948 customers and 1000 medians, without any particular calibration of the parallel method. The results indicate that, compared to sequential VNS, the cooperative strategy yields significant gains in terms of computation time without a loss in solution quality.     

Dirichlet duality and the nonlinear Dirichlet problem

We study the Dirichlet problem for fully nonlinear, degenerate elliptic equations of the form F (Hess u) = 0 on a smoothly bounded domain Ω ? ?ⁿ. In our approach the equation is replaced by a subset F ? Sym²(?ⁿ) of the symmetric n × n matrices with ?F ? { F = 0}. We establish the existence and uniqueness of continuous solutions under an explicit geometric “F‐convexity” assumption on the boundary ?Ω. We also study the topological structure of F‐convex domains and prove a theorem of Andreotti‐Frankel type. Two key ingredients in the analysis are the use of “subaffine functions” and “Dirichlet duality.” Associated to F is a Dirichlet dual set F? that gives a dual Dirichlet problem. This pairing is a true duality in that the dual of F? is F, and in the analysis the roles of F and F? are interchangeable. The duality also clarifies many features of the problem including the appropriate conditions on the boundary. Many interesting examples are covered by these results including: all branches of the homogeneous Monge‐Ampère equation over ?, ?, and ?; equations appearing naturally in calibrated geometry, Lagrangian geometry, and p‐convex Riemannian geometry; and all branches of the special Lagrangian potential equation. © 2008 Wiley Periodicals, Inc.     

Basic subgroups in modular abelian group algebras

Suppose F is a perfect field of char F = p ≠ 0 and G is an arbitrary abelian multiplicative group with a p-basic subgroup B and p-component G _p . Let FG be the group algebra with normed group of all units V(FG) and its Sylow p-subgroup S(FG), and let I _p (FG; B) be the nilradical of the relative augmentation ideal I(FG; B) of FG with respect to B. The main results that motivate this article are that 1 + I _p (FG; B) is basic in S(FG), and B(1 + I _p (FG; B)) is p-basic in V(FG) provided G is p-mixed. These achievements extend in some way a result of N. Nachev (1996) in Houston J. Math. when G is p-primary. Thus the problem of obtaining a (p-)basic subgroup in FG is completely resolved provided that the field F is perfect. Moreover, it is shown that G _p (1 + I _p (FG; B))/G _p is basic in S(FG)/G _p , and G(1 + I _p (FG; B))/G is basic in V(FG)/G provided G is p-mixed. As consequences, S(FG) and S(FG)/G _p are both starred or divisible groups. All of the listed assertions enlarge in a new aspect affirmations established by us in Czechoslovak Math. J. (2002), Math. Bohemica (2004) and Math. Slovaca (2005) as well.     

Stationary tail asymptotics of a tandem queue with feedback

Motivated by applications in manufacturing systems and computer networks, in this paper, we consider a tandem queue with feedback. In this model, the i.i.d. interarrival times and the i.i.d. service times are both exponential and independent. Upon completion of a service at the second station, the customer either leaves the system with probability p or goes back, together with all customers currently waiting in the second queue, to the first queue with probability 1−p. For any fixed number of customers in one queue (either queue 1 or queue 2), using newly developed methods we study properties of the exactly geometric tail asymptotics as the number of customers in the other queue increases to infinity. We hope that this work can serve as a demonstration of how to deal with a block generating function of GI/M/1 type, and an illustration of how the boundary behaviour can affect the tail decay rate.     

On Spectral Synthesis for Contractive p-Norms and Besov Spaces

We prove that spectral synthesis is possible for a general function space F _p with a contractive p-norm, namely, any quasi-continuous function in F _p vanishing q.e. outside an open set G can be approximated in this norm by continuous functions in F _p with compact support in G. The result is applied to contractive Besov spaces over d-sets in R ^N and censored stable processes over N-sets.     

Smoothing Newton Method for Minimizing the Sum of <Emphasis Type="Italic">p</Emphasis>-Norms

Consider the problem of minimizing the sum of p-norms, where p is a fixed real number in the interval [1,2]. This nondifferentiable problem arises in many applications, including the VLSI (very-large-scale-integration) layout problem, the facilities location problem and the Steiner minimum tree problem under a given topology. In this paper, we establish the optimality conditions, duality and uniqueness results for the problem. We then present a smoothing Newton method by the semismooth equations which are derived from the optimality conditions. The method is globally and superlinearly convergent, and moreover, it is quadratically convergent when p∈[1,3/2]∪{2}. Particularly, the quadratic convergence is proved for the case wherep∈(1,3/2]∪{2} without requiring strict complementarity. Preliminary numerical results are reported, which indicate that the method proposed is extremely promising. The work was supported by the Starting-Up Foundation (B13-B6050640) of Guangdong Province.     

Commutative Group Algebras of Cardinality {\cal N} 1

We let FG be the group algebra of an abelian group G over a field F with characteristic p. Also, we define G_p and S(FG) as the groups of all p-primary normed elements in G and FG, respectively. We prove that if G_p is Hausdorff and both F and G have cardinalities not exceeding ₁, then S(FG)/G_p is a direct sum of cyclics. Thus G_p is a direct factor of S(FG), and in particular G is a direct factor of the group of all normalized units V(FG), provided that the torsion part of G is a p-group. This answers a question posed by us in Hokkaido Math. J. (2000). Moreover we establish that if G is p-splitting, then any F-isomorphism of the group algebras FG and FH implies that H is p-splitting. We also show that if G is of power ₁ whose p-component G_p is a direct sum of torsion-complete groups and F has power p, then the F-isomorphism of FG and FH for any group H yields an isomorphism between G_p and H_p. In particular, when G is of power ₁ and is p-mixed of torsion-free rank 1 whose G_p is torsion-complete, we have G H. If F is in power p and G, with cardinality ₁, is a direct sum of p-local algebraically compact groups such that FG FH as F-algebras for some group H, then G H. These statements extend results due to Beers-Richman-Walker (1983), and also partially solve a well-known question raised by May in 1979.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

p-Median theorems for competitive locations

In competitive location theory, one wishes to optimally choose the locations ofr facilities to compete againstp existing facilities for providing service (or goods) to the customers who are at given discrete points (or nodes). One normally assumes that: (a) the level of demand of each customer is fixed (i.e. this demand is not a function of how far a customer is from a facility), and (b) the customer always uses the closest available facility. In this paper we study competitive locations when one or both of the above assumptions have been relaxed. In particular, we show that for each case and under certain assumptions, there exists a set of optimal locations which consists entirely of nodes.This work was supported by a National Science Foundation Grant ECS-8121741.     

Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces

For a real square-free multivariate polynomial F, we treat the general problem of finding real solutions of the equation F=0, provided that the real solution set {F=0}_ℝ is compact. We allow that the equation F=0 may have singular real solutions. We are going to decide whether this equation has a non-singular real solution and, if this is the case, we exhibit one for each generically smooth connected component of {F=0}_ℝ. We design a family of elimination algorithms of intrinsic complexity which solves this problem. In the worst case, the complexity of our algorithms does not exceed the already known extrinsic complexity bound of (nd) ^O(n) for the elimination problem under consideration, where n is the number of indeterminates of F and d its (positive) degree. In the case that the real variety defined by F is smooth, there already exist algorithms of intrinsic complexity that solve our problem. However, these algorithms cannot be used in case when F=0 admits F-singular real solutions.     

IndecomposableA-module summands inH * V which are unstable algebras

Letp be a prime and denote byA the modp Steenrod algebra. We determine the indecomposableA-module summands ofH*((ℤ/p)) ^d ;F _p which admit the structure of an unstableA-algebra. In fact, it turns out that this is equivalent to the problem of determining those indecomposableA-module summands which arise as the modp cohomology of a space (or even a classifying space of a finite group). We reduce this problem to one in modular representation theory, namely for whichd andp is the projective cover of the trivial one dimensional GL(d,F _p ) representationF _p a permutation module. Our solution of this latter problem makes use of the classification of subgroups of GL(d,F _p ) acting transitively on (F _p ) ^d \{0} and hence depends on the classification of finite simple groups (on Feit-Thompson's odd order theorem ifp=2).     

Set covering location models with stochastic critical distances

This paper formulates a new version of set covering models by introducing a customer-determined stochastic critical distance. In this model, all services are provided at the sites of facilities, and customers have to go to the facility sites to obtain the services. Due to the randomness of their critical distance, customers patronize a far or near facility with a probability. The objective is to find a minimum cost set of facilities so that every customer is covered by at least one facility with an average probability greater than a given level α. We consider an instance of the problem by embedding the exponential effect of distance into the model. An algorithm based on two searching paths is proposed for solutions to the instance. Experiments show that the algorithm performs well for problems with greater α, and the experimental results for smaller α are reported and analysed.     

The budget constrained r-interdiction median problem with capacity expansion

In this article, we elaborate on a budget constrained extension of the r-interdiction median problem with fortification (RIMF). The objective in the RIMF is to find the optimal allocation of protection resources to a given service system consisting of p facilities so that the disruptive effects of r possible attacks to the system are minimized. The defender of the system needs to fortify q facilities of the present system to offset the worst-case loss of r non-fortified facilities due to an interdiction in which the attacker’s objective is to cause the maximum possible disruption in the service level of the system. The defender-attacker relationship fits a bilevel integer programming (BIP) formulation where the defender and attacker take on the respective roles of the leader and the follower. We adopt this BIP formulation and augment it with a budget constraint instead of a predetermined number of facilities to be fortified. In addition, we also assume that each facility has a flexible service capacity, which can be expanded at a unit cost to accommodate the demand of customers who were serviced by some other interdicted facility before the attack. First, we provide a discrete optimization model for this new facility protection planning scenario with a novel set of closest assignment constraints. Then, to tackle this BIP problem we use an implicit enumeration algorithm performed on a binary tree. For each node representing a different fortification scheme, the attacker’s problem is solved to optimality using Cplex 11. We report computational results obtained on a test bed of 96 randomly generated instances. The article concludes with suggestions for future research.     

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.