Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
From MaRDI portal
Publication:973008
DOI10.1007/s00453-008-9248-1zbMath1208.90149MaRDI QIDQ973008
Vitaly A. Strusevich, Hans Kellerer
Publication date: 28 May 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9248-1
single machine scheduling; FPTAS; quadratic knapsack; total weighted completion time; availability constraints; scheduling agents
90B35: Deterministic scheduling theory in operations research
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines, Approximate and exact merging of knapsack constraints with cover inequalities, A lifted-space dynamic programming algorithm for the quadratic knapsack problem, Competitive two-agent scheduling with release dates and preemption on a single machine, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product, Semi-online scheduling on a single machine with unexpected breakdown, Minimizing total weighted completion time with an unexpected machine unavailable interval, Parallel machines scheduling with machine maintenance for minsum criteria, A strongly polynomial FPTAS for the symmetric quadratic knapsack problem, Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time, Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates, Approximation schemes for parallel machine scheduling with availability constraints, Single machine scheduling with semi-resumable machine availability constraints, 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, Approximability issues for unconstrained and constrained maximization of half-product related functions, Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, An iterated ``hyperplane exploration approach for the quadratic knapsack problem, A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem, The symmetric quadratic knapsack problem: approximation and scheduling applications, Solving 0-1 knapsack problems based on amoeboid organism algorithm, A PTAS for a class of binary non-linear programs with low-rank functions, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Minimizing total weighted late work on a single-machine with non-availability intervals, On the rectangular knapsack problem, Single machine scheduling with non-availability interval and optional job rejection, On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem, Single-machine scheduling with machine unavailability periods and resource dependent processing times, A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems, Approximation schemes for \(r\)-weighted minimization knapsack problems, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Scheduling with two competing agents to minimize total weighted earliness, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, A Dynamic Programming Heuristic for the Quadratic Knapsack Problem, Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time, Dual Techniques for Scheduling on a Machine with Varying Speed, Approximation of the Quadratic Knapsack Problem
Uses Software
Cites Work
- The quadratic knapsack problem -- a survey
- Single machine flow-time scheduling with a single breakdown
- Non-preemptive two-machine open shop scheduling with non-availability constraints
- Minimization of ordered, symmetric half-products
- Positive half-products and scheduling with controllable processing times
- Preemptive scheduling with availability constraints to minimize total weighted completion times
- New results on the completion time variance minimization
- An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
- Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
- Machine scheduling with an availability constraint
- Minimization of Half-Products
- Scheduling Problems with Two Competing Agents
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
