We view a facility system as a kind of supply chain and model it as a connected graph in which the nodes represent suppliers, distribution centers or customers and the edges represent the paths of goods or information...We view a facility system as a kind of supply chain and model it as a connected graph in which the nodes represent suppliers, distribution centers or customers and the edges represent the paths of goods or information. The efficiency, and hence the reliability, of a facility system is to a large degree adversely affected by the edge failures in the network. In this paper, we consider facility systems' reliability analysis based on the classical p-median problem when subject to edge failures. We formulate two models based on deterministic case and stochastic case to measure the loss in efficiency due to edge failures and give computational results and reliability envelopes for a specific example.展开更多
This paper uses a finite dominating set （FDS） to investigate the multi-facility ordered median problem （OMP） in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS...This paper uses a finite dominating set （FDS） to investigate the multi-facility ordered median problem （OMP） in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS in the node set, which not only generalizes the FDS result provided by Kalcsics, et al. （2002）, but also extends the FDS result from the single-facility Case to the multiple case, filling an important gap. Then, based on this FDS result, the authors develop an exact algorithm to solve the problem. However, if the number of facilities is large, it is not practical to find the optimal solution, because the multi-facility OMP in directed networks is NP-hard. Hence, we present a constant-approximation algorithm for the p-median problem in directed networks. Finally, we pose an open problem for future research.展开更多
The nestedness property has become an increasingly important means for devising efficient algorithms for network location problems.There have been attempts to explore the nestedness property of network location proble...The nestedness property has become an increasingly important means for devising efficient algorithms for network location problems.There have been attempts to explore the nestedness property of network location problems with some special cases of the convex ordered median objectives.However,there is little research on the nestedness property for those problems with the concave ordered median objectives.This paper constructs a tree network T and shows that the nestedness property cannot hold for the concave ordered median problem,which fills a gap in the research on the nestedness property.Finally,the authors pose an open problem on identifying the nestedness property for the continuous strategic ordered median problem.展开更多
The k-median problem has attracted a number of researchers. However,few of them have considered both the dynamic environment and the issue of accuracy. In this paper,a new type of query is studied,called continuous me...The k-median problem has attracted a number of researchers. However,few of them have considered both the dynamic environment and the issue of accuracy. In this paper,a new type of query is studied,called continuous median monitoring （CMM） query. It considers the k-median problem under dynamic environment with an accuracy guarantee. A continuous group nearest neighbor based （CGB） algorithm and an average distance medoid （ADM） algorithm are proposed to solve the CMM problem. ADM is a hill climbing schemed algorithm and achieves a rapid converging speed by checking only qualified candidates. Experiments show that ADM is more efficient than CGB and outperforms the classical PAM （partitioning around medoids） and CLARANS （clustering large applications based on randomized search） algorithms with various parameter settings.展开更多
In this note a simple proof of the famous Fermat-Torricelli problem is given. For the vertices of a given triangle, Fermat asks for a fourth point such that the sum of its Euclidean distances to the three given points...In this note a simple proof of the famous Fermat-Torricelli problem is given. For the vertices of a given triangle, Fermat asks for a fourth point such that the sum of its Euclidean distances to the three given points is minimized. Many authors present geometric approaches to the Fermat-Torricelli problem. We solve the problem by analytic and geometrical method and extend it to the sphere, we also characterize the median point P on the general regular surface.展开更多
The box constrained variational inequality problem can be reformulated as a nonsmooth equation by using median operator.In this paper,we present a smoothing Newton method for solving the box constrained variational in...The box constrained variational inequality problem can be reformulated as a nonsmooth equation by using median operator.In this paper,we present a smoothing Newton method for solving the box constrained variational inequality problem based on a new smoothing approximation function.The proposed algorithm is proved to be well defined and convergent globally under weaker conditions.展开更多
文摘We view a facility system as a kind of supply chain and model it as a connected graph in which the nodes represent suppliers, distribution centers or customers and the edges represent the paths of goods or information. The efficiency, and hence the reliability, of a facility system is to a large degree adversely affected by the edge failures in the network. In this paper, we consider facility systems' reliability analysis based on the classical p-median problem when subject to edge failures. We formulate two models based on deterministic case and stochastic case to measure the loss in efficiency due to edge failures and give computational results and reliability envelopes for a specific example.
基金This research is supported by the National Natural Science Foundation of China under Grant No. 70901050 and Macao Foundation under Grant No. 0144.
文摘This paper uses a finite dominating set （FDS） to investigate the multi-facility ordered median problem （OMP） in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS in the node set, which not only generalizes the FDS result provided by Kalcsics, et al. （2002）, but also extends the FDS result from the single-facility Case to the multiple case, filling an important gap. Then, based on this FDS result, the authors develop an exact algorithm to solve the problem. However, if the number of facilities is large, it is not practical to find the optimal solution, because the multi-facility OMP in directed networks is NP-hard. Hence, we present a constant-approximation algorithm for the p-median problem in directed networks. Finally, we pose an open problem for future research.
基金supported by the Macao Foundation under Grant No.0249National Natural Science Foundation of China under Grant No.70901050
文摘The nestedness property has become an increasingly important means for devising efficient algorithms for network location problems.There have been attempts to explore the nestedness property of network location problems with some special cases of the convex ordered median objectives.However,there is little research on the nestedness property for those problems with the concave ordered median objectives.This paper constructs a tree network T and shows that the nestedness property cannot hold for the concave ordered median problem,which fills a gap in the research on the nestedness property.Finally,the authors pose an open problem on identifying the nestedness property for the continuous strategic ordered median problem.
文摘The k-median problem has attracted a number of researchers. However,few of them have considered both the dynamic environment and the issue of accuracy. In this paper,a new type of query is studied,called continuous median monitoring （CMM） query. It considers the k-median problem under dynamic environment with an accuracy guarantee. A continuous group nearest neighbor based （CGB） algorithm and an average distance medoid （ADM） algorithm are proposed to solve the CMM problem. ADM is a hill climbing schemed algorithm and achieves a rapid converging speed by checking only qualified candidates. Experiments show that ADM is more efficient than CGB and outperforms the classical PAM （partitioning around medoids） and CLARANS （clustering large applications based on randomized search） algorithms with various parameter settings.
文摘In this note a simple proof of the famous Fermat-Torricelli problem is given. For the vertices of a given triangle, Fermat asks for a fourth point such that the sum of its Euclidean distances to the three given points is minimized. Many authors present geometric approaches to the Fermat-Torricelli problem. We solve the problem by analytic and geometrical method and extend it to the sphere, we also characterize the median point P on the general regular surface.
基金Supported by the NNSF of China（11071041）Supported by the Fujian Natural Science Foundation（2009J01002）Supported by the Fujian Department of Education Foundation（JA11270）
文摘The box constrained variational inequality problem can be reformulated as a nonsmooth equation by using median operator.In this paper,we present a smoothing Newton method for solving the box constrained variational inequality problem based on a new smoothing approximation function.The proposed algorithm is proved to be well defined and convergent globally under weaker conditions.
