We present the first constant-factor approximation algorithms for the following problem. Given a metric space (V, c), a finite set D subset of V of terminals/customers with demands d : D -> R+, a facility opening c...
详细信息
We present the first constant-factor approximation algorithms for the following problem. Given a metric space (V, c), a finite set D subset of V of terminals/customers with demands d : D -> R+, a facility opening cost f is an element of R+ and a capacity u is an element of R+, find a partition D = D-1(boolean OR) over dot ... (boolean OR) over dotD(k) and Steiner trees T-i for D-i (i = 1,..., k) with c(E(T-i))+ d(D-i) <= u for i = 1,..., k such that Sigma(k)(i=1) c(E(T-i))+ kf is minimum. This problem arises in VLSI design. It generalizes the bin-packing problem and the Steiner tree problem. In contrast to other network design and facility location problems, it has the additional feature of upper bounds on the service cost that each facility can handle. Among other results, we obtain a 4.5-approximation in polynomial time, a 4.5-approximation in cubic time, and a 5-approximation as fast as computing a minimum spanning tree on (D, c).
We consider the offline scheduling problem of minimizing the makespan on m parallel and identical machines with certain *** job and machine are labeled with the grade of service(GoS) levels,and each job can only be pr...
详细信息
We consider the offline scheduling problem of minimizing the makespan on m parallel and identical machines with certain *** job and machine are labeled with the grade of service(GoS) levels,and each job can only be processed by the machine whose GoS level is no more than that of the *** this paper,we present a polynomial time approximation scheme(PTAS) with running time P(nlogn) for the special case where the GoS level is either 1 or 2,where the hidden constant depends exponentially on the reciprocal value of the desired *** solves an open problem left in[11]*** also present a new full polynomial time approximation scheme (FPTAS) with running time O(n) for the case where the number of machines is fixed.
Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoreti...
详细信息
Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers placement as a graph-embedding problem and designs approximation algorithms with provable bounds on the quality of the solution. In this article, we aim at unifying the above two directions. First, we extend the existing approximation algorithms for graph embedding in 1D and 2D grid to those for hypergraphs, which typically model circuits to be placed on a FPGA. We prove an approximation bound of O(d root logn log log n) for 1D, that is, linear arrangement and O(d log nlog log n) for the 2D grid, where d is the maximum degree of hyperedges and n, the number of vertices in the hypergraph. Next, we propose an efficient method based on linear arrangement of the CLBs and the notion of space-filling curves for placing the configurable logic blocks (CLBs) of a netlist on island-style FPGAs with an approximation guarantee of O((4)root log n root kd log log n), where k is the number of nets. For the set of FPGA placement benchmarks, the running time is near linear in the number of CLBs thus allowing for scalability towards large circuits. We obtained a 33x speed-up, on average, with only 1.31x degradation in the quality of the solution compared to that produced by the popular FPGA tool VPR, thereby demonstrating the suitability of this very fast method for FPGA placement, with a provable performance guarantee.
Base station location has a significant impact on network lifetime performance for a sensor network. For a multihop sensor network, this problem is particularly challenging due to its coupling with data routing. This ...
详细信息
Base station location has a significant impact on network lifetime performance for a sensor network. For a multihop sensor network, this problem is particularly challenging due to its coupling with data routing. This article presents an approximation algorithm that can guarantee (1-epsilon)-optimal network lifetime performance for base station placement problem with any desired error bound epsilon > 0. The proposed (1-epsilon)-optimal approximation algorithm is based on several novel techniques that makes it possible to reduce an infinite search space to a finite-element search space for base station location. The first technique used in this reduction is to discretize cost parameter (associated with energy consumption) with performance guarantee. Subsequently, the continuous search space can be broken up into a finite number of subareas. The second technique is to exploit the cost property of each subarea and represent it by a novel notion called fictitious cost point, each with guaranteed cost bounds. We give a proof that the proposed base station placement algorithm is (1-epsilon)-optimal. This approximation algorithm is simpler and faster than a state-of-the-art algorithm and represents the best known result to the base station placement problem.
A novel underwater localization algorithm for autonomous underwater vehicle(AUVs) is proposed. Taking aim at the high cost of the traditional "leader-follower" positioning,a "parallel" model is ado...
详细信息
A novel underwater localization algorithm for autonomous underwater vehicle(AUVs) is proposed. Taking aim at the high cost of the traditional "leader-follower" positioning,a "parallel" model is adopted to describe the localization problem. Under an unknown-but-bounded assumption for sensor noise,bearing and range measurements can be modeled as linear constraints on the configuration space of the AUVs. Merged these constraints,a convex polyhedron representing the set of all configurations consistent with the sensor measurements can be induced. Estimates for the uncertainty in the position of a single AUV or the relative positions of two or more AUVs can then be obtained by projecting this polyhedron into appropriate subspaces of the configuration space. The localization uncertain region for each AUV can be recovered by an approximation algorithm to realize underwater localization for multiple AUVs. The deduced theoretically and the simulated results show that it is an economical and practical localization method for the AUV swarm.
The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as adjacent paths around a cycle, such that the maximum congestion over any physical link in the cyc...
详细信息
The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as adjacent paths around a cycle, such that the maximum congestion over any physical link in the cycle is minimized. The problem is NP-complete in general, but solvable in polynomial time when all hyperedges contain exactly two vertices. In this paper, we first formulate the problem as an Integer Linear Program (ILP). Then, a solution with approximation bound of 1: 5(opt + 1) is presented by using a clockwise (2/3)-rounding algorithm, where opt denotes the optimal value of maximum congestion. To our knowledge, this is the best approximation bound known for the MCHEC problem.
An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + rho), where rho is the best approximation ratio for t...
详细信息
An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + rho), where rho is the best approximation ratio for the metric Steiner tree problem (and is about 1.55 so far). The previous best approximation algorithm for the multicast k-tree routing problem has a performance ratio of 4. Two techniques, weight averaging and tree partitioning, are developed to facilitate the algorithm design and analysis.
Let E be the product of the Middle Third Cantor set with itself,we prove that the minimal value of the inverse density of a special class of balls can be attained,denoted by h（E）,which gives an upper bound of the Ha...
详细信息
Let E be the product of the Middle Third Cantor set with itself,we prove that the minimal value of the inverse density of a special class of balls can be attained,denoted by h（E）,which gives an upper bound of the Hausdorff measure of E in the nature of *** also introduce an approximation method for calculating the exact value of h（E）.And then we get a new upper bound of the Hausdorff measure of E.
approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matchin...
详细信息
approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be solved in polynomial time. The weighted matching problem is to find a matching in an edge weighted graph that has maximum weight. The first polynomial-time algorithm for this problem was given by Edmonds in 1965. The fastest known algorithm for the weighted matching problem has a running time of O(nm + n(2) log n). Many real world problems require graphs of such large size that this running time is too costly. Therefore, there is considerable need for faster approximation algorithms for the weighted matching problem. We present a linear-time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3. This improves the previously best performance ratio of 1/2. Our algorithm is not only of theoretical interest, but because it is easy to implement and the constants involved are quite small it is also useful in practice.
＜正＞In this paper,we address the scheduling problem with rejection in which we can choose a subset of jobs to *** not to process any job incurs a corresponding *** consider the following problem for the first time:s...
详细信息
＜正＞In this paper,we address the scheduling problem with rejection in which we can choose a subset of jobs to *** not to process any job incurs a corresponding *** consider the following problem for the first time:scheduling with rejection to minimize the total weighted completion time with the constraint of total penalties on identical parallel machines,where the number of identical parallel machines is *** show that it is NP-hard and design a pseudo-polynomial time algorithm as well as an FPTAS through dynamic programming.
暂无评论