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
Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines, TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION, Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier, Packing Under Convex Quadratic Constraints, Fully polynomial-time approximation scheme for single machine scheduling with proportional-linear deteriorating jobs, 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, An FPTAS of minimizing total weighted completion time on single machine with position constraint, Approximation algorithms for scheduling with reservations, The subset sum game revisited, An EPTAS for scheduling on unrelated machines of few different types, Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work, Two-agent single-machine scheduling with release dates to minimize the makespan, Approximating single- and multi-objective nonlinear sum and product knapsack problems, 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, Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs, 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, Semi-online scheduling on two identical machines with a common due date to maximize total early work, Single-machine serial-batch delivery scheduling with two competing agents and due date assignment, 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., Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, Parallel-machine scheduling with time-dependent and machine availability constraints, Two-agent parallel-machine scheduling with rejection, Scheduling on parallel identical machines with late work criterion: offline and online cases, Multi-machine scheduling with interval constrained position-dependent processing times, 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, A PTAS for a class of binary non-linear programs with low-rank functions, Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works, Due date assignment and two-agent scheduling under multitasking environment, Strongly polynomial FPTASes for monotone dynamic programs, Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs, In memoriam: Gerhard Woeginger (1964--2022), A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems, Packing under convex quadratic constraints, Single machine scheduling with rejection to minimize the weighted makespan, Online learning for min-max discrete problems, Approximation schemes for subset-sums ratio problems, The proportionate flow shop total tardiness problem, Parallel-batch scheduling with deterioration and rejection on a single machine, Single-machine scheduling with operator non-availability to minimize total weighted completion time, Structural parameters for scheduling with assignment restrictions, Scheduling on a single machine and parallel machines with batch deliveries and potential disruption, Scheduling jobs with a V-shaped time-dependent processing time, Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints, Scheduling for gathering multitype data with local computations, Approximation schemes for \(r\)-weighted minimization knapsack problems, A review of four decades of time-dependent scheduling: main results, new topics, and open problems, Two-agent scheduling problems with the general position-dependent processing time, 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
