Given a set of n positive integers and a knapsack of capacity c, the Subset-Sum Problem is to find a subset the sum of which is closest to c without exceeding the value c. In this paper we present a fullypolynomial a...
详细信息
Given a set of n positive integers and a knapsack of capacity c, the Subset-Sum Problem is to find a subset the sum of which is closest to c without exceeding the value c. In this paper we present a fully polynomial approximation scheme which solves the Subset-Sum Problem with accuracy epsilon in time O{min n . 1/epsilon, n + 1/epsilon(2) log(1/epsilon}) and space O(n + 1/epsilon). This scheme has a better time and space complexity than previously known approximationschemes. Moreover, the scheme always finds the optimal solution if it is smaller than (1 - epsilon)c. Computational results show that the scheme efficiently solves instances with up to 5000 items with a guaranteed relative error smaller than 1/1000. (C) 2003 Elsevier Science (USA). All rights reserved.
A fully polynomial approximation scheme is presented for the problem of sequencing jobs for processing by a single machine so as to minimize total tardiness. This result is obtained by modifying the author's pseud...
详细信息
A fullypolynomial time approximationscheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approach...
详细信息
A fullypolynomial time approximationscheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approaches need O(n + 1/epsilon(3)) and O(n . 1/epsilon) space, respectively. Our new approximationscheme requires only O(n + 1/epsilon(2)) space while also reducing the running time.
We propose a fullypolynomial bicriteria approximationscheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known mat...
详细信息
We propose a fullypolynomial bicriteria approximationscheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then utilized to yield a fully polynomial approximation scheme. (C) 2003 Elsevier B.V. All nights reserved.
作者：
Mondal, Sakib A.Gen Motors R&D
India Sci Lab 3rd FloorCreator BldgIIPB Whitqfield Rd Bangalore 560066 Karnataka India
This article considers a job scheduling problem arising in JIT context where a job may incur both earliness and tardiness penalty and these penalties are dependent on the job as well as amount of earliness and tardine...
详细信息
This article considers a job scheduling problem arising in JIT context where a job may incur both earliness and tardiness penalty and these penalties are dependent on the job as well as amount of earliness and tardiness. Special cases of the problems have been shown to be NP-Complete. To the best of our knowledge, there is no fully polynomial approximation scheme (FPTAS) for this problem. This article proposes a FPTAS for the problem.
. In this paper we investigate two specific two-agent scheduling scenarios. In the first scenario, one agent's objective function is total weighted late work, the other agent's is any regular max-typ e cost fu...
详细信息
. In this paper we investigate two specific two-agent scheduling scenarios. In the first scenario, one agent's objective function is total weighted late work, the other agent's is any regular max-typ e cost function, and our goal is to find a feasible schedule which minimizes the first agent's objective function subject to the other agent's not exceeding a threshold. We present a pseudo-polynomial dynamic programming algorithm for the case with m parallel machines, and also design a fullypolynomial time approximationscheme for the single-machine case. In the second scenario, one agent's objective function is a general regular sum-type objective function, the other agent's is still any regular max-typ e cost function, and our goal to enumerate all Pareto-optimal solutions regarding two agents' objective functions. We present a polynomial algorithm for the single-machine case in which two agents' job sets are nondisjoint and the first agent's jobs are of an equal length, and also show the tightness of our established upper bound on the number of Pareto-optimal solutions.
We study scheduling problems with rejection on *** job consists of a processing time,a rejection cost,and a release *** goal is to minimize the makespan of the jobs accepted when the total rejection cost is not larger...
详细信息
We study scheduling problems with rejection on *** job consists of a processing time,a rejection cost,and a release *** goal is to minimize the makespan of the jobs accepted when the total rejection cost is not larger than a given ***,we verify that these problems are ***,for the multiprocessor scheduling problem with rejection,we give a pseudo-polynomial algorithm and two fully polynomial approximation schemes(FPTAS for short)for fixed positive integer m,where m is the number of *** the scheduling problem with rejection and the job with non-identical release time on m machines,we also design a pseudo-polynomial algorithm and a fully polynomial approximation scheme when m is a fixed positive *** provide an approximation algorithm with the worst case performance 2 for arbitrary positive integer ***,we discuss the online scheduling problem with *** show that even if there are just two distinct arrive times for the jobs,there is not any online algorithm whose competitive ratio is constant for it.
NP-hard cases of the single-item capacitated lot-sizing problem have been the topic of extensive research and continue to receive considerable attention. However. surprisingly few theoretical results have been publish...
详细信息
NP-hard cases of the single-item capacitated lot-sizing problem have been the topic of extensive research and continue to receive considerable attention. However. surprisingly few theoretical results have been published on approximation methods for these problems. To the best of our knowledge, until now no polynomialapproximation method is known that produces solutions with a relative deviation from optimality that is bounded by a constant. In this paper we show that such methods do exist by presenting an even stronger result: the existence of fully polynomial approximation schemes. The approximationscheme is first developed for a quite general model, which has concave backlogging and production cost functions and arbitrary (monotone) holding cost functions. Subsequently we discuss important special cases of the model and extensions of the approximationscheme to even more general models.
We present fully polynomial approximation schemes (FPASs) for the problem of minimizing completion time variance (CTV) of a set of n jobs on a single machine. The fastest of these schemes runs in time O(n(2)/epsilon) ...
详细信息
We present fully polynomial approximation schemes (FPASs) for the problem of minimizing completion time variance (CTV) of a set of n jobs on a single machine. The fastest of these schemes runs in time O(n(2)/epsilon) and thus improves on all fully polynomial approximation schemes presented in the literature. (C) 2002 Published by Elsevier Science B.V.
This paper considers the problem of processing n jobs in a two-machine non-preemptive open shop to minimize the makespan, i.e., the maximum completion time. One of the machines is assumed to be non-bottleneck. It is s...
详细信息
This paper considers the problem of processing n jobs in a two-machine non-preemptive open shop to minimize the makespan, i.e., the maximum completion time. One of the machines is assumed to be non-bottleneck. It is shown that, unlike its flow shop counterpart, the problem is NP-hard in the ordinary sense. On the other hand, the problem is shown to be solvable by a dynamic programming algorithm that requires pseudopolynomial time. The latter algorithm can be converted into a fully polynomial approximation scheme that runs in O(n(2)/epsilon) time. An O(n log n) approximation algorithm is also designed which finds a schedule with makespan at most 5/4 times the optimal value, and this bound is tight. (C) 1997 Elsevier Science B.V.
暂无评论