scientific article; zbMATH DE number 1305477

MaRDI QIDQ4252365zbMATH OpenFDO

Authors Gerhard J. Woeginger

Publication date 11 January 2000

zbMATH Keywords

combinatorial optimizationdynamic programmingfully polynomial time approximation schemescheduling

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Recommendations

• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Fully polynomial time approximation schemes for stochastic dynamic programs
• Structure of polynomial-time approximation
• A computationally efficient FPTAS for convex stochastic dynamic programs
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs

Cited in

(20)

• On-line scheduling with extendable working time on a small number of machines
• Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities
• On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems.
• A PTAS for the average weighted completion time problem on unrelated machines.
• Analysis of FPTASes for the multi-objective shortest path problem
• A theory and algorithms for combinatorial reoptimization
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Strongly polynomial FPTASes for monotone dynamic programs
• Approximating multidimensional subset sum and Minkowski decomposition of polygons
• Approximation schemes for a class of subset selection problems
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Designing PTASs for MIN-SUM scheduling problems
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• scientific article; zbMATH DE number 1594561 (Why is no real title available?)
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states
• The two single-machine scheduling problems with slack due date to minimize total early work and late work
• Polynomial time approximation schemes and parameterized complexity
• Approximation algorithms for extensible bin packing
• Scheduling linear deteriorating jobs with rejection on a single machine

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4252365)