An improved per-scenario bound for the two-stage stochastic facility location problem

We study the two-stage stochastic facility location problem(2-SFLP)by proposing an LP(location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem,improving the previously best per-scenario bound of 2.4957.     

The Mutation Game,Coxeter-Dynkin Graphs,and Generalized Root Systems

We introduce the mutation game on a directed multigraph,which is dual to Mozes5 numbers game.This new game allows us to create geometric and combinatorial structure that allows generalization of root systems to more general graphs.We interpret Coxeter-Dynkin diagrams in this multigraph context and exhibit new geometric forms for the associated root systems.     

Number and Location of Limit Cycles in a Class of Perturbed Polynomial Systems

In this paper,we investigate the number,location and stability of limit cycles in a class of perturbedpolynomial systems with (2n 1) or (2n 2)-degree by constructing detection function and using qualitativeanalysis.We show that there are at most n limit cycles in the perturbed polynomial system,which is similar tothe result of Perko in [8] by using Melnikov method.For n=2,we establish the general conditions dependingon polynomial's coefficients for the bifurcation,location and stability of limit cycles.The bifurcation parametervalue of limit cycles in [5] is also improved by us.When n=3 the sufficient and necessary conditions for theappearance of 3 limit cycles are given.Two numerical examples for the location and stability of limit cycles areused to demonstrate our theoretical results.     

Maximum Likelihood Estimator of the Location Parameter under Moving Extremes Ranked Set Sampling Design

Cost effective sampling design is a problem of major concern in some experiments especially when the measurement of the characteristic of interest is costly or painful or time consuming.In the current paper,a modification of ranked set sampling(RSS)called moving extremes RSS(MERSS)is considered for the estimation of the location parameter for location family.A maximum likelihood estimator(MLE)of the location parameter for this family is studied and its properties are obtained.We prove that the MLE is an equivariant estimator under location transformation.In order to give more insight into the performance of MERSS with respect to(w.r.t.)simple random sampling(SRS),the asymptotic efficiency of the MLE using MERSS w.r.t.that using SRS is computed for some usual location distributions.The relative results show that the MLE using MERSS can be real competitors to the MLE using SRS.     

GL method for solving equations in math-physics and engineering

In this paper, we propose a GL method for solving the ordinary and the partial differential equation in mathematical physics and chemics and engineering. These equations govern the acustic, heat, electromagnetic, elastic, plastic, flow, and quantum etc. macro and micro wave field in time domain and frequency domain. The space domain of the differential equation is infinite domain which includes a finite inhomogeneous domain. The inhomogeneous domain is divided into finite sub domains. We present the solution of the differential equation as an explicit recursive sum of the integrals in the inhomogeneous sub domains. Actualy, we propose an explicit representation of the inhomogeneous parameter nonlinear inversion. The analytical solution of the equation in the infinite homogeneous domain is called as an initial global field. The global field is updated by local scattering field successively subdomaln by subdomain. Once all subdomains are scattered and the updating process is finished in all the sub domains, the solution of the equation is obtained. We call our method as Global and Local field method, in short , GL method. It is different from FEM method, the GL method directly assemble inverse matrix and gets solution. There is no big matrix equation needs to solve in the GL method. There is no needed artificial boundary and no absorption boundary condition for infinite domain in the GL method. We proved several theorems on relationships between the field solution and Green＇s function that is the theoretical base of our GL method. The numerical discretization of the GL method is presented. We proved that the numerical solution of the GL method convergence to the exact solution when the size of the sub domain is going to zero. The error estimation of the GL method for solving wave equation is presented. The simulations show that the GL method is accurate, fast, and stable for solving elliptic, parabolic, and hyperbolic equations. The GL method has advantages and wide applications in the 3D electromagnetic （EM）     

Strong stability of Nash equilibria in load balancing games

We study strong stability of Nash equilibria in load balancing games of m(m 2)identical servers,in which every job chooses one of the m servers and each job wishes to minimize its cost,given by the workload of the server it chooses.A Nash equilibrium(NE)is a strategy profile that is resilient to unilateral deviations.Finding an NE in such a game is simple.However,an NE assignment is not stable against coordinated deviations of several jobs,while a strong Nash equilibrium(SNE)is.We study how well an NE approximates an SNE.Given any job assignment in a load balancing game,the improvement ratio(IR)of a deviation of a job is defined as the ratio between the pre-and post-deviation costs.An NE is said to be aρ-approximate SNE(ρ1)if there is no coalition of jobs such that each job of the coalition will have an IR more thanρfrom coordinated deviations of the coalition.While it is already known that NEs are the same as SNEs in the 2-server load balancing game,we prove that,in the m-server load balancing game for any given m 3,any NE is a(5/4)-approximate SNE,which together with the lower bound already established in the literature yields a tight approximation bound.This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games.To establish our upper bound,we make a novel use of a graph-theoretic tool.     

An approximation algorithm for the dynamic facility location problem with submodular penalties

In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.     

Fault-tolerant concave facility location problem with uniform requirements

In this paper, we consider the fault-tolerant concave facility location problem (FTCFL) with uni- form requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation fac- tor is proved to be 1.52.     

FAST ACOUSTIC IMAGING FOR A 3D PENETRABLE OBJECT IMMERSED IN A SHALLOW WATER WAVEGUIDE＊

The paper is concerned with the inverse problem for reconstructing a 3D penetrable ob- ject in a shallow water waveguide from the far-field data of the scattered fields with many acoustic point source incidences. An indicator sampling method is analyzed and presented for fast imaging the size, shape and location of such a penetrable object. The method has the advantages that a priori knowledge is avoided for the geometrical and material proper- ties of the penetrable obstacle and the much complicated iterative techniques are avoided during the inversion. Numerical examples are given of successful shape reconstructions for several 3D penetrable obstacles having a variety of shapes. In particular, numerical results show that the proposed method is able to produce a good reconstruction of the size, shape and location of the penetrable target even for the case where the incident and observation points are restricted to some limited apertures.     

SPECTRAL METHOD FOR ZAKHAROV EQUATION WITH PERIODIC BOUNDARY CONDITIONS

This paper describes the spectral method for numerically solving Zakharov equation with periodicboundary conditions. This method is spectral method for spatial variable and difference method fortime variable. We make error estimation of approximate solution and prove the convergence of spectralmethod. We had given the convergence rate. Also, we prove the stability of approximate method forinitial values.     

The k-level facility location game

We propose a cost-sharing scheme for the k-level facility location game that is cross-monotonic, competitive, and 6-approximate cost recovery. This extends the recent result for the 1-level facility location game of Pál and Tardos.     

设施选址博弈问题的无支付机制设计研究

选址博弈是目前国际相关学术领域的重要前沿课题之一. 在选址博弈问题中, 存在n个相互影响的``理性"居民, 他们的住址等信息是其私有信息;设计者需要设计选址机制, 以居民汇报的住址信息为输入, 输出设施位置. 在进行机制设计的过程中, 如何在没有金钱的刺激下, 保证所有居民``说真话", 设计出防策略性无支付机制是其中的重要研究内容. 设施选址博弈问题的无支付机制设计是组合优化和理论计算机科学的交叉学科课题, 在管理科学、信息科学以及社会经济学等领域有着重要的应用, 具有重要的理论意义和实际的应用价值. 现根据不同设施类型及个数、不同个人偏好、不同度量空间以及不同社会总体目标等条件, 介绍各种类型的设施选址博弈模型, 罗列相关的研究成果, 并总结其中尚待解决的问题.     

Noncooperative facility location games

A noncooperative game theoretical approach is considered for the multifacility location problem. It turns out that the facility location game is a potential game in the sense of Monderer and Shapley and some properties of the game are studied.     

Competitive facility location and design with reactions of competitors already in the market

A new retail facility is to locate and its service quality is to determine where similar facilities of competitors offering the same goods are already present. The market share captured by each facility depends on its distance to customers and its quality, which is described by a probabilistic Huff-like model. In order to maximize the profit of the new facility, a two-stage method is developed, which takes into account the reactions of the competitors. In the quality decision stage, the competitive decision process occurring among facilities is modelled as a game, whose solution is given by its Nash equilibrium. The solution, which can be represented as functions of the location of the new facility, is obtained by analytical resolution of a system of equations in the case of one facility in the market or by polynomial approximation in the case of multiple facilities. In the location decision stage, an interval based global optimization method is used to determine the best location of the new facility. Numerical experiments on randomly generated instances demonstrate the effectiveness of the method.     

A cross-monotonic cost sharing method for the facility location game with service installation costs

In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.     

A cross-monotonic cost-sharing scheme for the concave facility location game

In this paper, we present a cost-sharing scheme for the concave facility location game by exploring the concavity structure. We show that it is cross-monotonic and competitive, and recovers 1/3 fraction of the total cost.     

A Bilevel p-median model for the planning and protection of critical facilities

The bilevel p-median problem for the planning and protection of critical facilities involves a static Stackelberg game between a system planner (defender) and a potential attacker. The system planner determines firstly where to open p critical service facilities, and secondly which of them to protect with a limited protection budget. Following this twofold action, the attacker decides which facilities to interdict simultaneously, where the maximum number of interdictions is fixed. Partial protection or interdiction of a facility is not possible. Both the defender’s and the attacker’s actions have deterministic outcome; i.e., once protected, a facility becomes completely immune to interdiction, and an attack on an unprotected facility destroys it beyond repair. Moreover, the attacker has perfect information about the location and protection status of facilities; hence he would never attack a protected facility. We formulate a bilevel integer program (BIP) for this problem, in which the defender takes on the leader’s role and the attacker acts as the follower. We propose and compare three different methods to solve the BIP. The first method is an optimal exhaustive search algorithm with exponential time complexity. The second one is a two-phase tabu search heuristic developed to overcome the first method’s impracticality on large-sized problem instances. Finally, the third one is a sequential solution method in which the defender’s location and protection decisions are separated. The efficiency of these three methods is extensively tested on 75 randomly generated instances each with two budget levels. The results show that protection budget plays a significant role in maintaining the service accessibility of critical facilities in the worst-case interdiction scenario.     

Cooperative facility location games

The location of facilities in order to provide service for customers is a well-studied problem in the operations research literature. In the basic model, there is a predefined cost for opening a facility and also for connecting a customer to a facility, the goal being to minimize the total cost. Often, both in the case of public facilities (such as libraries, municipal swimming pools, fire stations, … ) and private facilities (such as distribution centers, switching stations, … ), we may want to find a ‘fair’ allocation of the total cost to the customers—this is known as the cost allocation problem. A central question in cooperative game theory is whether the total cost can be allocated to the customers such that no coalition of customers has any incentive to build their own facility or to ask a competitor to service them. We establish strong connections between fair cost allocations and linear programming relaxations for several variants of the facility location problem. In particular, we show that a fair cost allocation exists if and only if there is no integrality gap for a corresponding linear programming relaxation; this was only known for the simplest unconstrained variant of the facility location problem. Moreover, we introduce a subtle variant of randomized rounding and derive new proofs for the existence of fair cost allocations for several classes of instances. We also show that it is in general NP-complete to decide whether a fair cost allocation exists and whether a given allocation is fair.     

基于敌意风险分析方法的多阶段反恐设备选址模型

恐怖袭击一直是人类安全的重要威胁之一。随着当前恐怖袭击在全球的频发,对反恐问题的研究更加急迫。针对反恐设施选址问题,考虑资源分配的多阶段性以及动态性,根据贝叶斯决策理论和序贯博弈思想,构建了多阶段反恐设施的敌意风险分析决策模型。讨论在城市多个设施点离散选址的不同情况下,通过预防性和修复性的资源分配将恐怖袭击的损失降低到最小。以上海市区县网络为例进行编程仿真测试,结果表明,模型可给出不同给定资源设定下的最优选址方案,是一种有效并切实可行的分析方法。