In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G=(V,E) with weights w:E -> a"currency sign(+), a set T (1),T (2),aEuro brok...
详细信息
In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G=(V,E) with weights w:E -> a"currency sign(+), a set T (1),T (2),aEuro broken vertical bar,T (k) of subtrees of G is called a tree cover of G if . In the Min-Max k-tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in Arkin et al. (J. algorithms 59:1-18, 2006) and Even et al. (Oper. Res. Lett. 32(4):309-315, 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of (Xu and Wen in Oper. Res. Lett. 38:169-173, 2010). In the Bounded Tree Cover problem we are given graph G and a bound lambda and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most lambda. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in Arkin et al. (J. algorithms 59:1-18, 2006).
Previous literature on very large scale integration routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each "terminal" consists of ...
详细信息
Previous literature on very large scale integration routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each "terminal" consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layout steps such as wiring estimation. In this paper, we address the general problem of minimum-cost routing tree construction in the presence of multiport terminals, which gives rise to the group Steiner minimal tree problem. Our main result is the first known approximation algorithm for the group Steiner problem with a sublinear performance bound. In particular, for a net with k multiport terminals, previous heuristics have a performance bound of (k - 1) . OPT, while our construction offers an improved performance bound of 2 . (2 + 1n(k/2)) . rootk . OPT. Our Java implementation is available on the Web.
Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a ...
详细信息
Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the sphere;(ii) maximizing a multilinear form over a Cartesian product of spheres;and (iii) maximizing a multiquadratic form over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time approximation algorithms for them. By reducing the above problems to that of determining the L(2)-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Omega ((log n/n)(d/2-1)) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Omega ((1/n)(d/2-1)) in the literature. We believe that our approach will find further applications in the design of approximation algorithms for polynomial optimization problems with provable guarantees.
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class c(...
详细信息
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class c(e) and size s(e). The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d. In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into N bins, such that, the total size of all items and shelf divisors packed in any bin is at most 1 + epsilon for a given epsilon > 0 and N is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most C different classes.
We obtain improved algorithms for finding small vertex covers in bounded degree graphs and hypergraphs. We use semidefinite programming to relax the problems and introduce new rounding techniques for these relaxations...
详细信息
We obtain improved algorithms for finding small vertex covers in bounded degree graphs and hypergraphs. We use semidefinite programming to relax the problems and introduce new rounding techniques for these relaxations. On graphs with maximum degree at most Delta, the algorithm achieves a performance ratio of 2 - (1 - o(1))2 ln ln Delta/ln Delta for large Delta, which improves the previously known ratio of 2 - log Delta+ O (1)/Delta obtained by Halldorsson and Radhakrishnan. Using similar techniques, we also present improved approximations for the vertex cover problem in hypergraphs. For k-uniform hypergraphs with n vertices, we achieve a ratio of k - (1 - o(1)) k ln ln n/ln n for large n, and for k - uniform hypergraphs with maximum degree at most Delta the algorithm achieves a ratio of k - (1 - o(1))k(k-1) ln ln Delta/ln Delta for large Delta. These results considerably improve the previous best ratio of k(1 - c/Delta 1/k-1) for bounded degree k - uniform hypergraphs, and k(1 - c/n k-1/k) for general k - uniform hypergraphs, both obtained by Krivelevich. Using similar techniques, we also obtain an approximation algorithm for the weighted independent set problem, matching a recent result of Halldorsson.
This article focuses on the problem of coflow scheduling with precedence constraints in identical parallel networks, a well-known NP -hard problem. Coflow is a relatively new network abstraction that characterizes com...
详细信息
This article focuses on the problem of coflow scheduling with precedence constraints in identical parallel networks, a well-known NP -hard problem. Coflow is a relatively new network abstraction that characterizes communication patterns in data centers. When considering workload sizes and weights that are dependent on the network topology in the input instances, the proposed algorithm for the flow-level scheduling problem achieves an approximation ratio of O(chi) where chi is the coflow number of the longest path in the directed acyclic graph (DAG). Additionally, when taking into account topology-dependent workload sizes, the algorithm achieves an approximation ratio of O(R chi) , where R represents the ratio of maximum weight to minimum weight. For the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O(m chi) , where m is the number of network cores when considering workload sizes and weights that are topology-dependent. Moreover, when considering topology-dependent workload sizes, the algorithm achieves an approximation ratio of O(Rm chi) . In the coflows of multi-stage job scheduling problem, the proposed algorithm achieves an approximation ratio of O(chi) . Although our theoretical results are based on a limited set of input instances, experimental findings show that the results for general input instances outperform the theoretical results.
In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, c...
详细信息
In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is Omega(n Omega(1))-hard to approximate on general metrics, we obtain an O(logn)-approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2+E is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O(E) term.
In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classic...
详细信息
In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. This problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp 805-814, 2009). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria -approximations where the algorithm returns a solution whose cost is within factor of the optimum and violates the capacity constraints within factor . Shmoys et al. (Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp 265-274, 1997) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply (O(1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). These are the first algorithms with constant approximation in which the viol
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is 27/35. The other is for undirect...
详细信息
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is 27/35. The other is for undirected graphs and its approximation ratio is 7/8 - o(1). Both algorithms improve on the previous bests.
We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths (EDP) problem, we are given a network G with source-sink pairs (s(i), t(i)), 1 less than or equal to i less than or ...
详细信息
We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths (EDP) problem, we are given a network G with source-sink pairs (s(i), t(i)), 1 less than or equal to i less than or equal to k, and the goal is to find a largest subset of source-sink pairs that can be simultaneously connected in an edge-disjoint manner. We show that in directed networks, for any epsilon > 0, EDP is NP-hard to approximate within m(1/2-epsilon) We also design simple approximation algorithms that achieve essentially matching approximation guarantees for some generalizations of EDP. Another related class of routing problems that we study concerns EDP with the additional constraint that the routing paths be of bounded length. We show that, for any epsilon > 0, bounded length EDP is hard to approximate within m(1/2-epsilon) even in undirected networks, and give an O(rootm)-approximation algorithm for it. For directed networks, we show that even the single source-sink pair case (i.e. find the maximum number of paths of bounded length between a given source-sink pair) is hard to approximate within m(1/2-epsilon), for any epsilon > 0. (C) 2003 Elsevier Science (USA). All rights reserved.
暂无评论