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.
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 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
The skew of an edge-weighted rooted tree is the maximum difference between any two root-to-leaf path weights. Zero- or bounded-skew trees are needed for achieving synchronization in many applications, including networ...
详细信息
The skew of an edge-weighted rooted tree is the maximum difference between any two root-to-leaf path weights. Zero- or bounded-skew trees are needed for achieving synchronization in many applications, including network multicasting [G. N. Rouskas and I. Baldine, IEEE J. on Selected Areas in Communication, 15 (1997), pp, 346-356] and VLSI clock routing [H. Bakoglu, Circuits, Interconnections, and Packaging for VSLI, Addison-Wesley, Reading, MA, 1990, A. B. Kahng and G. Robins, On Optimal Interconnections for VSLI, Kluwer Academic Publishers, Norwell, MA, 1995]. In these applications edge weights represent propagation delays, and a signal generated at the root should be received by multiple recipients located at the leaves (almost) simultaneously. The objective is to find zero- or bounded-skew trees of minimum total weight, since the weight of the tree is directly proportional to the amount of resources (bandwidth and buffers for network multicasting, power and chip area for clock routing in VLSI) that must be allocated to the tree. Charikar et al. in [Proceedings of the Tenth ACH-SIAM Symposium on Discrete algorithms, Baltimore, MD, 1999, ACM, New York, 1999, pp. 177-184] have recently proposed the first strongly polynomial algorithms with proven constant approximation factors, 2e approximate to 5.44 and 16.86, for finding minimum weight zero- and bounded-skew trees, respectively. In this paper we introduce a new approach to these problems, based on zero-skew "stretching" of spanning trees, and obtain algorithms with improved approximation factors of 4 and 14. For the case when tree nodes are points in the plane and edge weights are given by the rectilinear metric our algorithms find zero- and bounded-skew trees of length at most 3 and 9 times the optimum. This case is of special interest in VLSI clock routing. An important feature of our algorithms is their practical running time, which is asymptotically the same as the time needed for computing the minimum spanning
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.
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.
The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may ne...
详细信息
The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m "subjobs" and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.
暂无评论