In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)\ . \C-max, where the numbers m(1) and m(2) of machines available in the two stages are part of the input. We demonstrate the...
详细信息
In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)\ . \C-max, where the numbers m(1) and m(2) of machines available in the two stages are part of the input. We demonstrate the existence of a polynomial time approximation scheme for this problem. This result solves the simplest case of an open problem that has been posed by Leslie Hall in a recent paper (Hall, 1995). hn extension of our algorithm yields an approximation scheme for the closely related two-stage multiprocessor job shop problem. (C) 2000 Elsevier Science B.V. All rights reserved.
Given a set N of n terminals in the first quadrant of the Euclidean plane E-2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertic...
详细信息
Given a set N of n terminals in the first quadrant of the Euclidean plane E-2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called rectilinear Steiner arborescence problem, which has been proved to be NP-complete recently (Shi and Su, 11th ACM-SIAM Symposium on Discrete algorithms (SODA), January 2000, to appear). In this paper, we present a polynomial time approximation scheme for this problem.
We present a new polynomial time approximation scheme (PTAS) for tree alignment, which is an important variant of multiple sequence alignment. As in the existing PTASs in the literature, the basic approach of our algo...
详细信息
We present a new polynomial time approximation scheme (PTAS) for tree alignment, which is an important variant of multiple sequence alignment. As in the existing PTASs in the literature, the basic approach of our algorithm is to partition the given tree into overlapping components of a constant size and then apply local optimization on each such component. But the new algorithm uses a clever partitioning strategy and achieves a better efficiency for the same performance ratio. For example, to achieve approximation ratios 1.6 and 1.5, the best existing PTAS has to spend time O(kdn(5)) and O(kdn(9)), respectively, where n is the length of each leaf sequence and d, k are the depth and number of leaves of the tree, while the new PTAS only has to spend time O(kdn(4)) and O(kdn(5)). Moreover, the performance of the PTAS is more sensitive to the size of the components, which basically determines the running time, and we obtain an improved approximation ratio for each size. Some experiments of the algorithm on simulated and real data are also given.
This paper addresses the performance of list scheduling a cyclic set of N non-preemptive dependent generic tasks on m identical processors. The reduced precedence graph is assumed to be strongly connected but the numb...
详细信息
This paper addresses the performance of list scheduling a cyclic set of N non-preemptive dependent generic tasks on m identical processors. The reduced precedence graph is assumed to be strongly connected but the number of simultaneously active instances of a generic task is not restricted to be at most one. Some properties on arbitrary schedules are first given. Then, we restrict to regular schedules for which it is shown that the number of ready or active tasks at any instant is at least the minimum height H* of a directed circuit of the reduced precedence graph. The average cycle time of any regular list schedule is then shown to be at most (2 - (min{H*, m}/m)) times the absolute minimum average cycle time. This result, which is similar well-known (2 - (1/m)) Graham's bound applying for non-cyclic scheduling, shows to what extent regular list schedules take the: parallelism of the cyclic task system into account. (C) 2000 Elsevier Science B.V. All rights reserved.
The feedback vertex set problem for hypergraphs is considered and an efficient approximation algorithm is presented. It is shown that an approximation factor of k is guaranteed when the cardinality of every hyperedge ...
详细信息
The feedback vertex set problem for hypergraphs is considered and an efficient approximation algorithm is presented. It is shown that an approximation factor of k is guaranteed when the cardinality of every hyperedge is bounded by an integer k, generalizing the existing result for ordinary graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one pro...
详细信息
Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.
A typical approach to estimate an unknown quantity mu is to design an experiment that produces a random variable Z distributed in [0, 1] with E[Z] = mu, run this experiment independently a number of times, and use the...
详细信息
A typical approach to estimate an unknown quantity mu is to design an experiment that produces a random variable Z distributed in [0, 1] with E[Z] = mu, run this experiment independently a number of times, and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [ 0, 1]. We describe an approximation algorithm AA which, given and, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+epsilon of mu with probability at least 1-delta. We prove that the expected number of experiments run by AA (which depends on Z) is optimal to within a constant factor for every Z.
The World Wide Web provides access to vast amounts of information, but content providers are considering charging for the information and services they supply. Thus the consumer may face the problem of balancing the b...
详细信息
The World Wide Web provides access to vast amounts of information, but content providers are considering charging for the information and services they supply. Thus the consumer may face the problem of balancing the benefit of asking for information against the cost (in terms of both money and time) of acquiring it. We study information-gathering strategies that maximize the expected value to the consumer. In our model there is a single information request, which has a known benefit to the consumer. To satisfy the request, queries can be sent simultaneously or in sequence to any of a finite set of independent information sources. For each source we know the monetary cost of making the query, the amount of time it will take, and the probability that the source will be able to provide the requested information. A policy specifies which sources to contact at which times, and the expected value of the policy can be defined as some function of the likelihood that the policy will yield an answer, the expected benefit, and the monetary cost and time delay associated with executing the policy. The problem is to nd an expected-value-maximizing policy. We explore four variants of the objective function V: (i) V consists only of the benefit term subject to threshold constraints on both total cost and total elapsed time, (ii) V is linear in the expected total cost of the policy subject to the constraint that the total elapsed time never exceeds some deadline, (iii) V is linear in the expected total elapsed time subject to the constraint that the total cost never exceeds some threshold, and (iv) V is linear in the expected total monetary cost and the expected time delay of the policy. The problems of devising an optimal querying policy for all four variants and approximating an optimal querying policy for variants (iii) and (iv) are shown to be NP-hard. For (i), and with a mild simplifying assumption for (iii), we give a fully polynomial time approximation scheme. For (ii), we c
We propose a new cutting plane heuristic for the classical stable roommates problem. Our approach utilises a new linear programming formulation for the problem, and the underlying geometric properties of the fractiona...
详细信息
We propose a new cutting plane heuristic for the classical stable roommates problem. Our approach utilises a new linear programming formulation for the problem, and the underlying geometric properties of the fractional solution to construct the violated inequality. We test the approach on moderate size problems, with encouraging computational performance. To further illustrate the versatility of this approach, we also show how it can be suitably extended to handle variants of the basic stable roommates model. (C) 2000 Elsevier Science B.V. All rights reserved.
In this paper, we study a new version of multiple sequence alignment, fixed topology alignment with recombination. We show that it cannot be approximated within any constant ratio unless P = NP. For a restricted versi...
详细信息
In this paper, we study a new version of multiple sequence alignment, fixed topology alignment with recombination. We show that it cannot be approximated within any constant ratio unless P = NP. For a restricted version, we show that the problem is MAX-SNP-hard. This implies that there is no PTAS for this version unless P = NP. We also propose approximation algorithms for a special case, where each internal node has at most one recombination child and any two merge paths for different recombination nodes do not share any common node. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论