China
Africa
Explore chapters and articles related to this topic
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
It would be nice if we have an approximation scheme whose running time is a polynomial function of both n and k. Such an approximation scheme is called a fully polynomial-time approximation scheme. Indeed, for 0/1-Knapsack Optimization, there is a FPTAS due to Ibarra and Kim [5]. The idea of the method of Ibarra and Kim is to scale down the value of each item, use the pseudo-polynomial algorithm given in Section 2.5 to obtain an exact solution for the scaled down version, and then output the items obtained in the exact solution. The net effect of scaling down the value of each item is to reduce the running time of the algorithm in such a way that accuracy loss is limited. Most FPTAS reported in the literature exploit pseudopolynomial algorithms in this manner. Thus, one of the significances of developing pseudo-polynomial algorithms is that they can be converted into FPTAS.
Optimization Techniques in Routing
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
In this section, we present and describe a fully polynomial-time approximation scheme for the fractional global routing problem. Carden et al. in 1996 [22] were the first to apply a multicommodity flow approximation algorithm to global routing. They use the approximation algorithm by Shahrokhi and Matula [3]. The approximation scheme presented here, first published in Ref. [9], is based on the approximation scheme by Garg and Könemann [6], but also use ideas from Fleischer [7]. The approximation scheme iteratively finds Steiner trees with respect to dual lengths ye, then adjusts the dual lengths just for the Steiner tree found.
Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty
Published in Engineering Optimization, 2022
Byung-Cheon Choi, Myoung-Ju Park, Kyung Min Kim
This section shows that Problem P1 with a fixed number k is weakly NP-hard and has no fully polynomial-time approximation scheme (FPTAS), while it has a polynomial-time approximation scheme (PTAS). Note that FPTAS and PTAS are approximation schemes returning approximate solution whose objective value is at most times the optimal solution for a minimization problem for a given parameter . The run-time of an FPTAS is polynomial in the problem size and in while the run-time of a PTAS is polynomial in the problem size for each specific , but might be exponential in . Finally, it is proved that the case with an arbitrary number k cannot be approximated.