首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 78 毫秒
1.
In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.  相似文献   

2.
In this paper, we propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended Lagrangian multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in P-median problem to recast it as another equivalent global optimization problem over the space of the extended Lagrangian multipliers. Then we present a stochastic search algorithm to find the extended Lagrangian multipliers corresponding to the optimal solution of the original P-median problem. Numerical experiments illustrate that the proposed algorithm can effectively find a global optimal or very good suboptimal solution to the underlying P-median problem, especially for the computationally challenging subclass of P-median problems with a large gap between the optimal solution of the original problem and that of its Lagrangian relaxation.  相似文献   

3.
In this paper, the p-median and p-centre problems are generalized by considering the possibility that one or more of the facilities may become inactive. The unreliable p-median problem is defined by introducing the probability that a facility becomes inactive. The (p, q)-centre problem is defined when p facilities need to be located but up to q of them may become unavailable at the same time. An heuristic procedure is presented for each problem. A rigorous procedure is discussed for the (p, q)-centre problem. Computational results are presented.  相似文献   

4.
The classical p-median problem is discussed, together with methods for its solution. The multi-median problem, a generalization of the p-median problem in which more than one type of facility is allowed, is introduced and methods of solution developed. Numerical results are presented.  相似文献   

5.
The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.  相似文献   

6.
An ordered median function is used in location theory to generalize a class of problems, including median and center problems. In this paper we consider the complexity of inverse ordered 1-median problems on the plane and on trees, where the multipliers are sorted nondecreasingly. Based on the convexity of the objective function, we prove that the problems with variable weights or variable coordinates on the line are NP-hard. Then we can directly get the NP-hardness result for the corresponding problem on the plane. We finally develop a cubic time algorithm that solves the inverse convex ordered 1-median problem on trees with relaxation on modification bounds.  相似文献   

7.
In this paper we consider two medi-centre location problems. One is the m-medi-centre problem in which we add to the m-median problem uniform distance constraints. The other problem is the uncapacitated medi-centre facility location problem where we include the fixed costs of establishing the facilities and thus the number of facilities is also a decision variable. For the two problems we present algorithms and discuss computational experience.  相似文献   

8.
Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.  相似文献   

9.
The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 n vertices, n ? 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.  相似文献   

10.
Consider the resource allocation problem:minimize ∑ni=1 fi(xi) subject to ∑ni=1 xi = N and xi's being nonnegative integers, where each fi is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n2(log N)2] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号