共查询到20条相似文献,搜索用时 781 毫秒
1.
We consider the k-level facility location problem with soft capacities (k-LFLPSC). In the k-LFLPSC, each facility i has a soft capacity u i along with an initial opening cost f i ≥ 0, i.e., the capacity of facility i is an integer multiple of u i incurring a cost equals to the corresponding multiple of f i . We firstly propose a new bifactor (ln(1/β)/(1 ?β),1+2/(1 ?β))-approximation algorithm for the k-level facility location problem (k-LFLP), where β ∈ (0, 1) is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation. 相似文献
2.
A particular continuous single facility minimax location problem on the surface of a hemisphere is discussed. We assume that all the demand points are equiweighted. An algorithm, based on spherical trigonometry, for finding the minimax point is presented. The minimax point thus obtained is unique and the algorithm is O(n
2) in the worst case. 相似文献
3.
The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFLβ[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D1,D2,…,Dh−1 of locations that may open an intermediate transmission station and a set Dh of locations of clients. Each client in Dh must be serviced by an open transmission station in Dh−1 and every open transmission station in Dl must be serviced by an open transmission station on the next lower level, Dl−1. An open transmission station on the first level, D1 must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is cij. For iF, the cost of opening a facility at location i is fi0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem. 相似文献
4.
The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand
points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that
lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs
required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185,
2005). We show that their algorithm is wrong and further present a correct O(n
3) algorithm for the same. We also propose an O(n
2) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs
without an increase in time complexity. 相似文献
5.
6.
设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步. 相似文献
7.
Justo Puerto Antonio M. Rodríguez-Chía 《Mathematical Methods of Operations Research》2006,63(1):31-51
In this paper we analyze a new location problem which is a generalization of the well-known single facility location model.
This extension consists of introducing a general objective function and replacing fixed locations by trajectories. We prove
that the problem is well-stated and solvable. A Weiszfeld type algorithm is proposed to solve this generalized dynamic single
facility location problem on L
p
spaces of functions, with p ∈(1,2]. We prove global convergence of our algorithm once we have assumed that the set of demand functions and the initial
step function belong to a subspace of L
p
called Sobolev space. Finally, examples are included illustrating the application of the model to generalized regression
analysis and the convergence of the proposed algorithm. The examples also show that the pointwise extension of the algorithm
does not have to converge to an optimal solution of the considered problem while the proposed algorithm does. 相似文献
8.
This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling.
We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding
a feasible solution whose approximation ratio is less than 2+(9/4)/(n−1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio
using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation
algorithms with a constant approximation ratio, which is less than 2+3/4. 相似文献
9.
Ankit Aggarwal Anand Louis Manisha Bansal Naveen Garg Neelima Gupta Shubham Gupta Surabhi Jain 《Mathematical Programming》2013,141(1-2):527-547
We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of ${3+2\sqrt{2}}$ for the same algorithm. We also provide an example which shows that any local search algorithm which uses only these three operations cannot achieve an approximation guarantee better than 3. 相似文献
10.
Motivated by considerations of pure state entanglement in quantum information, we consider the problem of finding the best rank-1 approximation to an arbitrary r -th order tensor. Reformulating the problem as an optimization problem on the Lie group SU (n1) ⊗ … ⊗ SU (nr) of so-called local unitary transformations and exploiting its intrinsic geometry yields a new approach, which finally leads to Riemannian variant of the conjugate gradient algorithm. Numerical simulations support that our method offers an alternative to the higher-order power method for computing the best rank-1 approximation to a tensor. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
11.
Philip N Klein Serge A Plotkin Satish Rao Éva Tardos 《Journal of Algorithms in Cognition, Informatics and Logic》1997,22(2):241-269
In this paper we consider theSteiner multicutproblem. This is a generalization of the minimum multicut problem where instead of separating nodepairs, the goal is to find a minimum weight set of edges that separates all givensetsof nodes. A set is considered separated if it is not contained in a single connected component. We show anO(log3(kt)) approximation algorithm for the Steiner multicut problem, wherekis the number of sets andtis the maximum cardinality of a set. This improves theO(t log k) bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecifiedknode pairs. In this paper we describe anO(log2 k) approximation algorithm for this directed multicut problem. Ifk ? n, this represents an improvement over theO(log n log log n) approximation algorithm that is implied by the technique of Seymour. 相似文献
12.
We present a polynomial algorithm with time complexity O(n 5) and approximation ratio 4/3 (plus some additive constant) for the minimum 2-peripatetic salesman problem in a complete n-vertex graph with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1, 2)-min-2w). This result improves the available algorithm for this problem with approximation ratio 11/7. 相似文献
13.
E. Kh. Gimadi 《Journal of Applied and Industrial Mathematics》2011,5(2):212-220
In order to solve the location problem in the p-median form we present an approximation algorithm with time complexity O(n
2) and the results of its probabilistic analysis. The input data are defined on a complete graph with distances between the
vertices expressed by the independent random variables with the same uniform distribution. The value of the objective function
produced by the algorithm amounts to a certain sum of the random variables that we analyze basing on an estimate for the probabilities
of large deviations of these sums. We use a limit theorem in the form of the Petrov inequalities, taking into account the
dependence of the random variables in the sum. The probabilistic analysis yields some estimates for the relative error and
the failure probability of our algorithm, as well as conditions for its asymptotic exactness. 相似文献
14.
We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line coloring algorithm with a performance ratio ofO(n/log n), an improvement of
factor over the previous best known algorithm of Vishwanathan. Also, from the same principles, we construct a parallel coloring algorithm with the same performance ratio, for the first such result. As a byproduct, we obtain a parallel approximation for the independent set problem. 相似文献
15.
In the capacitated facility location problem with hard capacities, we are given a set of facilities, ${\mathcal{F}}$ , and a set of clients ${\mathcal{D}}$ in a common metric space. Each facility i has a facility opening cost f i and capacity u i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set ${\mathcal{F}}$ and assign each client to an open facility so that at most u i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by the distance c ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs. The only known approximation algorithms that deliver solutions within a constant factor of optimal for this NP-hard problem are based on local search techniques. It is an open problem to devise an approximation algorithm for this problem based on a linear programming lower bound (or indeed, to prove a constant integrality gap for any LP relaxation). We make progress on this question by giving a 5-approximation algorithm for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. One notable aspect of our algorithm is that it relies on partitioning the input into a collection of single-demand capacitated facility location problems, approximately solving them, and then combining these solutions in a natural way. 相似文献
16.
The goal of this paper is to find a low‐rank approximation for a given nth tensor. Specifically, we give a computable strategy on calculating the rank of a given tensor, based on approximating the solution to an NP‐hard problem. In this paper, we formulate a sparse optimization problem via an l1‐regularization to find a low‐rank approximation of tensors. To solve this sparse optimization problem, we propose a rescaling algorithm of the proximal alternating minimization and study the theoretical convergence of this algorithm. Furthermore, we discuss the probabilistic consistency of the sparsity result and suggest a way to choose the regularization parameter for practical computation. In the simulation experiments, the performance of our algorithm supports that our method provides an efficient estimate on the number of rank‐one tensor components in a given tensor. Moreover, this algorithm is also applied to surveillance videos for low‐rank approximation. 相似文献
17.
F. R. B. Cruz G. R. Mateus J. MacGregor Smith 《Journal of Mathematical Modelling and Algorithms》2003,2(1):37-56
Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, and electric power systems. A model for multi-level network design is formulated as a mixed-integer program. The approach is innovative because it integrates in the same model aspects of discrete facility location, topological network design, and dimensioning. We propose a branch-and-bound algorithm based on Lagrangian relaxation to solve the model. Computational results for randomly generated problems are presented showing the quality of our approach. We also present and discuss a real world problem of designing a two-level local access urban telecommunication network and solving it with the proposed methodology. 相似文献
18.
Elisabeth Gassner 《Annals of Operations Research》2009,172(1):393-404
This paper deals with downgrading the 1-median, i.e., changing values of parameters within certain bounds such that the optimal
objective value of the location problem with respect to the new values is maximized. We suggest a game-theoretic view at this
problem which leads to a characterization of an optimal solution. This approach is demonstrated by means of the Downgrading
1-median problem in the plane with Manhattan metric and implies an O(nlog2n)\mathcal {O}(n\log^{2}n) time algorithm for this problem. 相似文献
19.
The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O(n log n q- m)-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph. 相似文献
20.
We present two heuristic methods for solving the Discrete Ordered Median Problem (DOMP), for which no such approaches have
been developed so far. The DOMP generalizes classical discrete facility location problems, such as the p-median and p-center. The first procedure proposed in this paper is based on a genetic algorithm developed by Moreno Vega (1996) for p-median and p-center problems. Additionally, a second heuristic approach based on the Variable Neighborhood Search metaheuristic (VNS)
proposed by Hansen and Mladenović (1997) for the p-median problem is described. An extensive numerical study is presented to show the efficiency of both heuristics and compare
them. 相似文献