When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
From MaRDI portal
Publication:4427320
DOI10.1287/ijoc.12.1.57.11901zbMath1034.90014OpenAlexW2136658137MaRDI QIDQ4427320
Publication date: 6 November 2003
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.12.1.57.11901
Related Items
Approximation schemes for scheduling a maintenance and linear deteriorating jobs ⋮ Two-machine open-shop scheduling with rejection to minimize the makespan ⋮ Semi-online scheduling on two identical machines with a common due date to maximize total early work ⋮ Approximating multidimensional subset sum and Minkowski decomposition of polygons ⋮ Single-machine serial-batch delivery scheduling with two competing agents and due date assignment ⋮ Packing Under Convex Quadratic Constraints ⋮ Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks ⋮ The economic lot-sizing problem with an emission capacity constraint ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Complexity and approximability of scheduling resumable proportionally deteriorating jobs ⋮ The finite horizon investor problem with a budget constraint ⋮ Fully polynomial-time approximation scheme for single machine scheduling with proportional-linear deteriorating jobs ⋮ Approximation schemes for a class of subset selection problems ⋮ Single machine scheduling with rejection to minimize the weighted makespan ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ Online learning for min-max discrete problems ⋮ Approximation schemes for subset-sums ratio problems ⋮ Parallel-machine scheduling with time-dependent and machine availability constraints ⋮ Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines ⋮ The proportionate flow shop total tardiness problem ⋮ Two-agent parallel-machine scheduling with rejection ⋮ Single-machine scheduling with production and rejection costs to minimize the maximum earliness ⋮ Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work ⋮ Scheduling resumable deteriorating jobs on a single machine with non-availability constraints ⋮ Two-agent single-machine scheduling with release dates to minimize the makespan ⋮ Complexity and approximability results for slicing floorplan designs. ⋮ Approximating single- and multi-objective nonlinear sum and product knapsack problems ⋮ An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand ⋮ Parallel-batch scheduling with deterioration and rejection on a single machine ⋮ An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs ⋮ Scheduling with rejection and non-identical job arrivals ⋮ Single-machine scheduling with operator non-availability to minimize total weighted completion time ⋮ Approximation scheme for single-machine rescheduling with job delay and rejection ⋮ Single machine scheduling with assignable due dates to minimize maximum and total late work ⋮ Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems ⋮ General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems ⋮ Toward a model for backtracking and dynamic programming ⋮ Scheduling on parallel identical machines with late work criterion: offline and online cases ⋮ Scheduling of pipelined operator graphs ⋮ Bounded parallel-batching scheduling with two competing agents ⋮ Bi-criteria scheduling on a single parallel-batch machine ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width ⋮ Scheduling on a single machine and parallel machines with batch deliveries and potential disruption ⋮ Scheduling jobs with a V-shaped time-dependent processing time ⋮ Multi-machine scheduling with interval constrained position-dependent processing times ⋮ Scheduling a variable maintenance and linear deteriorating jobs on a single machine ⋮ Bin covering with cardinality constraints ⋮ Evolutionary algorithms and dynamic programming ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Complex-demand scheduling problem with application in smart grid ⋮ Production and Transportation Integration for Commit-to-Delivery Mode with General Shipping Costs ⋮ Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs ⋮ Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs ⋮ Scheduling for gathering multitype data with local computations ⋮ \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION ⋮ Limitations of incremental dynamic programming ⋮ Scheduling on parallel machines with preemption and transportation delays ⋮ Minimization of ordered, symmetric half-products ⋮ A stronger model of dynamic programming algorithms ⋮ Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications ⋮ A comment on parallel-machine scheduling under a grade of service provision to minimize makespan ⋮ An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure ⋮ Parallel-machine scheduling with deteriorating jobs and rejection ⋮ Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date ⋮ Approximation of the supply scheduling problem ⋮ ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation ⋮ Differential approximation schemes for half-product related functions and their scheduling applications ⋮ Approximation algorithms for scheduling with reservations ⋮ Approximation schemes for \(r\)-weighted minimization knapsack problems ⋮ The subset sum game revisited ⋮ A note on dual approximation algorithms for class constrained bin packing problems ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ Approximation algorithms for single machine scheduling with one unavailability period ⋮ A PTAS for a class of binary non-linear programs with low-rank functions ⋮ POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION ⋮ Weighted sum coloring in batch scheduling of conflicting jobs ⋮ The single-machine total tardiness scheduling problem: review and extensions ⋮ Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities ⋮ Equivalent time-dependent scheduling problems ⋮ Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works ⋮ A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem ⋮ Due date assignment and two-agent scheduling under multitasking environment ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Two-agent scheduling problems with the general position-dependent processing time ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ In memoriam: Gerhard Woeginger (1964--2022) ⋮ Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier ⋮ A comment on scheduling two parallel machines with capacity constraints ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ An FPTAS of minimizing total weighted completion time on single machine with position constraint ⋮ Offline black and white bin packing ⋮ Packing under convex quadratic constraints ⋮ The focus of attention problem
