Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying th...
详细信息
Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them. We give polynomial-time reductions from this problem and variants to the (un)capacitated facility location problem, directly yielding approximation algorithms, two with constant factors in the metric case, one with a logarithmic factor in the general case. Published by Elsevier B.V.
In the Fault-Tolerant Facility Placement problem (FTFP) we are given a set of customers C, a set of sites F, and distances between customers and sites. We assume that the distances satisfy the triangle inequality. Eac...
详细信息
In the Fault-Tolerant Facility Placement problem (FTFP) we are given a set of customers C, a set of sites F, and distances between customers and sites. We assume that the distances satisfy the triangle inequality. Each customer j has a demand r(j) and each site may open an unbounded number of facilities. The objective is to minimize the total cost of opening facilities and connecting each customer j to r(j) different open facilities. We present two LP-rounding algorithms for FTFP. The first algorithm achieves an approximation ratio of 4. The second algorithm uses the method of filtering to improve the ratio to 3.16. Published by Elsevier B.V.
Minimum Diameter Color Spanning Set (MDCSS) on a given set of colored points is the problem of selecting one point from each color such that the diameter of the selected points gets minimized. In this paper, we presen...
详细信息
Minimum Diameter Color Spanning Set (MDCSS) on a given set of colored points is the problem of selecting one point from each color such that the diameter of the selected points gets minimized. In this paper, we present some approximation algorithms and show some results on approximability of this problem in low and high dimensions. (C) 2018 Published by Elsevier B.V.
We describe approximation algorithms with bounded performance guarantees for the following problem: A graph is given with edge weights satisfying the triangle inequality, together with two numbers k and p. Find k disj...
详细信息
We describe approximation algorithms with bounded performance guarantees for the following problem: A graph is given with edge weights satisfying the triangle inequality, together with two numbers k and p. Find k disjoint subsets of p vertices each, so that the total weight of edges within subsets is maximized. (C) 1997 Elsevier Science B.V.
We show that for the anti-ferromagnetic Ising model on the Bethe lattice, weak spatial mixing implies strong spatial mixing. As a by-product of our analysis, we obtain what is to the best of our knowledge the first ri...
详细信息
We show that for the anti-ferromagnetic Ising model on the Bethe lattice, weak spatial mixing implies strong spatial mixing. As a by-product of our analysis, we obtain what is to the best of our knowledge the first rigorous proof of the uniqueness threshold for the anti-ferromagnetic Ising model (with non-zero external field) on the Bethe lattice. Following a method due to Weitz [15], we then use the equivalence between weak and strong spatial mixing to give a deterministic fully polynomial time approximation scheme for the partition function of the anti-ferromagnetic Ising model with arbitrary field on graphs of degree at most , throughout the uniqueness region of the Gibbs measure on the infinite -regular tree. By a standard correspondence, our results translate to arbitrary two-state anti-ferromagnetic spin systems with soft constraints. Subsequent to a preliminary version of this paper, Sly and Sun [13] have shown that our results are optimal in the sense that, under standard complexity theoretic assumptions, there does not exist a fully polynomial time approximation scheme for the partition function of such spin systems on graphs of maximum degree for parameters outside the uniqueness region. Taken together, the results of [13] and of this paper therefore indicate a tight relationship between complexity theory and phase transition phenomena in two-state anti-ferromagnetic spin systems.
The problem of scheduling independent tasks on uniform processors in order to minimize the maximum completion time of the schedule is strongly NP-complete. Therefore, the existence of a polynomial or even a pseudo-pol...
详细信息
The problem of scheduling independent tasks on uniform processors in order to minimize the maximum completion time of the schedule is strongly NP-complete. Therefore, the existence of a polynomial or even a pseudo-polynomial time algorithm is very unlikely unless P = NP. This paper deals with approximation schemes which attempt to find a solution in polynomial time that is close to the optimal solution. Specifically, two variants of LPT scheduling are shown: one which is polynomial time and the other a probabilistically good algorithm.
In this article we present approximation algorithms for the Arc Orienteering Problem (AOP). We propose a polylogarithmic approximation algorithm in directed graphs, while in undirected graphs we give a (6 + epsilon + ...
详细信息
In this article we present approximation algorithms for the Arc Orienteering Problem (AOP). We propose a polylogarithmic approximation algorithm in directed graphs, while in undirected graphs we give a (6 + epsilon + o(1)) and a (4 + epsilon)-approximation algorithm for arbitrary instances and instances of unit profit, respectively. Also, an inapproximability result for the AOP is obtained as well as approximation algorithms for the Mixed Orienteering Problem. (C) 2014 Elsevier B.V. All rights reserved.
We introduce the class cover problem, a variant of disk cover with forbidden regions, with applications to classification and facility location problems. We prove similar hardness results to disk cover. We then presen...
详细信息
We introduce the class cover problem, a variant of disk cover with forbidden regions, with applications to classification and facility location problems. We prove similar hardness results to disk cover. We then present a polynomial-time approximation algorithm for class cover that performs within a ln n + 1 factor of optimal, which is nearly tight under standard hardness assumptions. In the special case that the points lie in a d-dimensional space with Euclidean norm, for some fixed constant d, we obtain a polynomial time approximation scheme.
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set...
详细信息
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Delta) + 2 and H(Delta) + 2 are presented, where Delta is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c(n) + 1) ln n where c(n) ln k is the approximation factor for the node weighted Steiner tree problem (currently c(n) = 1.6103). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c + 1)H(Delta) + c - 1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644).
We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in [T. Lengauer, J. Assoc. Comput. Mach., 36(1989), pp. 474-509] or are specifi...
详细信息
We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in [T. Lengauer, J. Assoc. Comput. Mach., 36(1989), pp. 474-509] or are specified by one-dimensional finite narrow periodic specifications as in [E. Wanke, Paths and cycles in finite periodic graphs, in Lecture Notes in Comp. Sci. 711, Springer-Verlag, New York, 1993, pp. 751-760]. We show that, for most of the problems Pi considered when specified using k-level-restricted hierarchical specifications or k-narrow periodic specifications, the following hold. (i) Let p be any performance guarantee of a polynomial time approximation algorithm for Pi, when instances are specified using standard specifications. Then For All epsilon > 0, Pi has a polynomial time approximation algorithm with performance guarantee (1 + epsilon)p. (ii) Pi has a polynomial time approximation scheme when restricted to planar instances. These are the first polynomial time approximation schemes for PSPACE-hard hierarchically or periodically specified problems. Since several of the problems considered are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximation schemes. This answers an open question in Condon et al. [Chicago J. Theoret. Comput. Sci., 1995, Article 4].
暂无评论