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.90014MaRDI 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
TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION, Approximation algorithms for scheduling with reservations, The focus of attention problem, Two-machine open-shop scheduling with rejection to minimize the makespan, The economic lot-sizing problem with an emission capacity constraint, General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems, Toward a model for backtracking and dynamic programming, Bi-criteria scheduling on a single parallel-batch machine, Scheduling a variable maintenance and linear deteriorating jobs on a single machine, Limitations of incremental dynamic programming, A stronger model of dynamic programming algorithms, Scheduling resumable deteriorating jobs on a single machine with non-availability constraints, Evolutionary algorithms and dynamic programming, Parallel-machine scheduling with deteriorating jobs and rejection, Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date, Differential approximation schemes for half-product related functions and their scheduling applications, Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks, An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, 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, ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation, Approximation algorithms for single machine scheduling with one unavailability period, 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, A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem, Complexity and approximability results for slicing floorplan designs., Two-agent parallel-machine scheduling with rejection, Complex-demand scheduling problem with application in smart grid, Scheduling on parallel machines with preemption and transportation delays, Minimization of ordered, symmetric half-products, Approximation of the supply scheduling problem, An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand, Offline black and white bin packing, Approximation schemes for scheduling a maintenance and linear deteriorating jobs, Approximating multidimensional subset sum and Minkowski decomposition of polygons, Complexity and approximability of scheduling resumable proportionally deteriorating jobs, The finite horizon investor problem with a budget constraint, Approximation schemes for a class of subset selection problems, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Single-machine scheduling with production and rejection costs to minimize the maximum earliness, Scheduling with rejection and non-identical job arrivals, Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems, Scheduling of pipelined operator graphs, Bounded parallel-batching scheduling with two competing agents, Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width, Bin covering with cardinality constraints, An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure, A comment on scheduling two parallel machines with capacity constraints, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs, A note on dual approximation algorithms for class constrained bin packing problems, POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION
