When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

References

• Ausiello G., Crescenzi P., Protasi M. Approximate Solution of NP Optimization Problems. Theoretical Computer Science (1995) 150:1–55Crossref, Google Scholar
• Ausiello G., D'Atri A., Protasi M. Structure Preserving Reductions Among Convex Optimization Problems. Journal of Computer and Systems Sciences (1980) 21:136–153Crossref, Google Scholar
• Ausiello G., Marchetti-Spaccamela A., Protasi M. Toward a Unified Approach for the Classification of NPComplete Optimization Problem. Theoretical Computer Science (1980) 12:83–96Crossref, Google Scholar
• Bellman R. E., Dreyfus S. E.Applied Dynamic Programming (1962) (Princeton University Press, Princeton) Crossref, Google Scholar
• Browne S., Yechiali U. Scheduling Deteriorating Jobs on a Single Processor. Operations Research (1990) 38:432–450Link, Google Scholar
• Brucker P., Kovalyov M. Y. Single Machine Batch Scheduling to Minimize the Weighted Number of Late Jobs. ZOR—Mathematical Methods of Operations Research (1996) 43:1–8Crossref, Google Scholar
• Bruno J. L., Coffman E. G., Sethi R. Scheduling Independent Tasks to Reduce Mean Finishing Time. Communications of the ACM (1974) 17:382–387Crossref, Google Scholar
• Cai X. Minimization of Agreeably Weighted Variance in Single Machine Systems. European Journal of Operational Research (1995) 85:576–592Crossref, Google Scholar
• Chen Z.-L. Parallel Machine Scheduling with Time Dependent Processing Times. Discrete Applied Mathematics (1996) 70:81–9Crossref, Google Scholar
• Eilon S., Chowdhury I. G. Minimizing Waiting Variance in the Single Machine Problem. Management Science (1977) 23:567–575Link, Google Scholar
• Florian M., Lenstra J. K., Rinnooy Kan A. H .G. Deterministic Production Planning: Algorithms and Complexity. Management Science (1980) 26:669–679Link, Google Scholar
• Garey M. R., Johnson D. S. 'Strong’ NP-Completeness Results: Motivation, Examples, and Implications. Journal of the ACM (1978) 25:499–508Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco) Google Scholar
• Gens G. V., Levner E. V. Fast Approximation Algorithms for Job Sequencing with Deadlines. Discrete Applied Mathematics (1981) 3:313–318Crossref, Google Scholar
• Grahan R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics (1979) 5:287–326Crossref, Google Scholar
• Hall N. G., Posner M. E. Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times about a Common Due Date. Operations Research (1991) 39:836–846Link, Google Scholar
• Hariri A. M .A., Potts C. N., Van Wassenhove L. N. Single Machine Scheduling to Minimize Total Weighted Late Work. ORSA Journal on Computing (1995) 7:232–242Link, Google Scholar
• Hochbaum D. S., Landy D. Scheduling with Batching: Minimizing the Weighted Number of Tardy Jobs. Operations Research Letters (1994) 16:79–86Crossref, Google Scholar
• Horowitz E., Sahni S. Computing Partitions with Applications to the Knapsack Problem. Journal of the ACM (1974) 21:277–292Crossref, Google Scholar
• Horowitz E., Sahni S. Exact and Approximate Algorithms for Scheduling Nonidentical Processors. Journal of the ACM (1976) 23:317–327Crossref, Google Scholar
• Ibarra O., Kim C. E. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. Journal of the ACM (1975) 22:463–468Crossref, Google Scholar
• Jurisch B., Kubiak W., Jozefowska J. Algorithms for Minclique Scheduling Problems. Discrete Applied Mathematics (1997) 72:115–139Crossref, Google Scholar
• Karp R. M., Miller R. E., Thatcher J. W. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations (1972) (Plenum Press, New York, pp) 85–104Crossref, Google Scholar
• Kovalyov M. Y., Kubiak W. A Fully Polynomial Time Approximation Scheme for the Weighted Earliness-Tardiness Problem, to appear in Operations Research. (1998) Google Scholar
• Kovalyov M. Y., Kubiak W. A Fully Polynomial Time Approximation Scheme for Minimizing Makespan of Deteriorating Jobs. Journal of Heuristics (1998) 3:287–297Crossref, Google Scholar
• Kovalyov M. Y., Potts C. N., Vanwassenhove L. N. A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work. Mathematics of Operations Research (1994) 19:86–93Link, Google Scholar
• Kubiak W. Completion Time Variance on a Single Machine Is Difficult. Operations Research Letters (1993) 14:49–59Crossref, Google Scholar
• Kubiak W., Van De Velde S. L. Scheduling Deteriorating Jobs to Minimize Makespan, to appear in Naval Research Logistics. (1998) Google Scholar
• Lawler E. L. A 'Pseudopolynomial’ Algorithm for Sequencing Jobs to Minimize Total Tardiness. Annals of Discrete Mathematics (1997) 1:331–342Crossref, Google Scholar
• Lawler E. L. Fast Approximation Schemes for Knapsack Problems. Mathematics of Operations Research (1979) 4:339–356Link, Google Scholar
• Lawler E. L. A Fully Polynomial Approximation Scheme for the Total Tardiness Problem. Operations Research Letters (1982) 1:207–208Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H .G., Shmoys D. B., Graves S .C., Rinnooy Kan A .H. G., Zipkin P. H. Sequencing and Scheduling: Algorithms and Complexity. In Logistics of Production and Inventory (1993) (North-Holland, Amsterdam, pp) 445–522Handbooks in Operations Research and Management Science 4Crossref, Google Scholar
• Lawler E. L., Moore J. M. A Functional Equation and its Application to Resource Allocation and Sequencing Problems. Management Science (1969) 16:77–84Link, Google Scholar
• Lenstra J. K. (1977) . Unpublished manuscriptGoogle Scholar
• Lenstra J. K., Rinnooy Kan A. H .G., Brucker P. Complexity of Machine Scheduling Problems. Annals of Discrete Mathematics (1977) 1:343–362Crossref, Google Scholar
• Paz A., Moran S. Non Deterministic Polynomial Optimization Problems and their Approximations. Theoretical Computer Science (1981) 15:251–277Crossref, Google Scholar
• Potts C. N., Van Wassenhove L. N. Single Machine Scheduling to Minimize Total Late Work. Operations Research (1992) 40:586–595Link, Google Scholar
• Potts C. N., Van Wassenhove L. N. Approximation Algorithms for Scheduling a Single Machine to minimize Total Late Work. Operations Research Letters (1992) 11:261–266Crossref, Google Scholar
• Sahni S. Algorithms for Scheduling Independent Tasks. Journal of the ACM (1976) 23:116–127Crossref, Google Scholar
• Van Hoesel C. P .M., Wagelmans A. P. M. Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems. Economic Institute Report 9735/A (1997) (Erasmus University, Rotterdam) Google Scholar
• Woeginger G. J. An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine. Technical Report Woe-21 (1998) (TU Graz, Austria) Google Scholar