A partitionable multiprocessor system can form multiple partitions, each consisting of a controller and a varying number of processors. Given such a system and a set of tasks, each of which can be executed on partitio...
详细信息
A partitionable multiprocessor system can form multiple partitions, each consisting of a controller and a varying number of processors. Given such a system and a set of tasks, each of which can be executed on partitions of varying sizes, we study the problem of choosing the partition sizes and a minimum completion time schedule for the execution of these tasks. We assume that the number of tasks to be scheduled on the system is no more than the maximum number of partitions that can be formed simultaneously by the system, and that parallelization of the tasks can achieve at most perfect speedup. We show this scheduling problem to be NP-hard, and present a polynomial time approximation algorithm for this problem. We derive a parameter dependent, asymptotically tight worst-case performance bound for this approximation algorithm. We also evaluate its average performance through simulation.
Consider a set of intervals S = {I-1, I-2, ... , I-n}, where I-i = (l(i), r(i)), l(i), and r(i) are real numbers, and l(i) < r(i). We study a restricted track assignment problem (RTAP): if an interval I-a contains ...
详细信息
Consider a set of intervals S = {I-1, I-2, ... , I-n}, where I-i = (l(i), r(i)), l(i), and r(i) are real numbers, and l(i) < r(i). We study a restricted track assignment problem (RTAP): if an interval I-a contains another interval I-b then I-a must be assigned to a higher track than I-b, and the goal is to minimize the number of tracks used. The problem RTAP is shown to be NP-hard. An approximation algorithm that produces a solution within twice of the optimal is also presented and the bound is shown to be tight. The algorithm runs in O(n log n) time and requires linear space. The proposed approximation algorithm is employed to solve the problem of finding a maximum-weighted independent set in a circle graph, and related problems.
We consider the following problem: given a collection of strings s1,...,s(m), find the shortest string s such that each s(i) appears as a substring (a consecutive block) of s. Although this problem is known to be NP-h...
详细信息
We consider the following problem: given a collection of strings s1,...,s(m), find the shortest string s such that each s(i) appears as a substring (a consecutive block) of s. Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2n), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4n. Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3n. We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.
We consider the following NP optimization problem: Given a set of polynomials P-i(x), i = 1,...,s, of degree at most 2 over GF[p] in n variables, find a root common to as many as possible of the polynomials P-i(x). We...
详细信息
We consider the following NP optimization problem: Given a set of polynomials P-i(x), i = 1,...,s, of degree at most 2 over GF[p] in n variables, find a root common to as many as possible of the polynomials P-i(x). We prove that in the case in which the polynomials do not contain any squares as monomials, it is always possible to approximate this problem within a factor of p(2)/(p - 1) in polynomial time for fixed p. This follows from the stronger statement that one can, in polynomial time, find an assignment that satisfies at least (p - 1)/p(2) of the nontrivial equations. More interestingly, we prove that approximating the maximal number of polynomials with a common root to within a factor of p-epsilon is NP-hard. This implies that the ratio between the performance of the approximation algorithm and the impossibility result is essentially p/(p - 1), which can be made arbitrarily close to 1 by choosing g large. We also prove that for any constant delta < 1, it is NP-hard to approximate the solution of quadratic equations over the rational numbers, or over the reals, within n(delta).
The bin packing problem is to pack a list of reals in (0, 1] into unit-capacity bins using the minimum number of bins. Let R[A] be the limiting worst value for the ratio A(L)/L* as L* goes to infinity, where A(L) deno...
详细信息
The bin packing problem is to pack a list of reals in (0, 1] into unit-capacity bins using the minimum number of bins. Let R[A] be the limiting worst value for the ratio A(L)/L* as L* goes to infinity, where A(L) denotes the number of bins used in the approximation algorithm A, and L* denotes the minimum number of bins needed to pack L. Obviously, R[A] reflects the worst-case behavior of A. For Next-k-Fit(NkF for short, k greater-than-or-equal-to 2), which is a linear time approximation algorithm for bin packing, it was known that 1.7 + 3/10(k-1) less-than-or-equal-to R[NkF] less-than-or-equal-to 2. In this paper, a tight bound R[NkF] = 1.7 + 3/10(k-1) is proved.
Given n demand points in the plane, the circle connecting problem (CCP) is to locate n circles in the plane, each with its center in a demand point, and determine the radius of each circle such that the corresponding ...
详细信息
Given n demand points in the plane, the circle connecting problem (CCP) is to locate n circles in the plane, each with its center in a demand point, and determine the radius of each circle such that the corresponding undirected graph G = (V, E), in which a vertex v(i) in V stands for the point p(i) and an edge (v(i), v(j)) in E if and only if p(i) and p(j) are located within the circle of each other, is connected, and the sum of the radii of these n circles is minimal. The constrained circle connecting problem is similar to the CCP except that the points are given in a plane with a set of obstacles and an edge (v(i), v(j)) in E if and only if p(i) and p(j) are located within the circle of each other and no obstacles exist between them. In this paper, we show that both these geometric problems are NP-hard. An O(n log n) time divide-and-conquer approximation algorithm that produces a solution no greater than twice an optimal one is also proposed for the two problems. Experimental results show that in the average case the approximate solution is close to the optimal solution.
The performance of a telecommunication system consisting of a set of transmitters without local buffers is modelled by a queueing network, and its tandem behavior is approximated in steady state. In this system, a fra...
详细信息
The performance of a telecommunication system consisting of a set of transmitters without local buffers is modelled by a queueing network, and its tandem behavior is approximated in steady state. In this system, a fraction of the units which as the instants of their arrival at each transmitter find it busy may retry to be processed by merging with the incoming arrival units at the same transmitter, after a fixed delay time. The performance of this system is approximated by a recursive algorithm. Furthermore, a numerical example is presented and the approximation outcomes are compared against those from a simulation study.
Let S be a set of messages to be routed on an N x N omega network. In addition, suppose that S contains communication conflicts. One strategy to deal with such conflicts is to partition S into some number of subsets, ...
详细信息
Let S be a set of messages to be routed on an N x N omega network. In addition, suppose that S contains communication conflicts. One strategy to deal with such conflicts is to partition S into some number of subsets, called rounds, such that each subset is conflict-free. The messages are then routed through the network by successively routing the messages in each subset. The minimum round partitioning problem is the problem of partitioning a given message set into a minimum number of rounds. We establish upper and lower bounds on the performance ratio for two heuristics for partitioning message patterns into rounds. For both of these heuristics we give upper and lower bounds of 0 (log N) and OMEGA (log N), respectively.
Mehlhorn (1988) has presented an improved implementation of the Kou, Markowsky and Berman Steiner tree approximation algorithm (1981). By replacing one step of the original algorithm the complexity reduces from O(\S\....
详细信息
Mehlhorn (1988) has presented an improved implementation of the Kou, Markowsky and Berman Steiner tree approximation algorithm (1981). By replacing one step of the original algorithm the complexity reduces from O(\S\.(\E\ + \V\.log\V\) to O(\E\ + \V\.log\V\), where S is the set of terminals, E the set of all edges and V the set of all vertices in the graph. In this paper we will show that due to the improvement two steps of the algorithm may be omitted. This does not reduce the complexity of the algorithm but it makes it simpler.
Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment...
详细信息
Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the optimal stable roommates problem is given in detail, and other applications are mentioned.
暂无评论