Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications

DOI10.1007/s00453-008-9248-1zbMath1208.90149OpenAlexW2093067798MaRDI 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

zbMATH Keywords

single machine schedulingFPTASquadratic knapsacktotal weighted completion timeavailability constraintsscheduling agents

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (38)

Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Dual Techniques for Scheduling on a Machine with Varying Speed ⋮ Semi-online scheduling on a single machine with unexpected breakdown ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Approximation of the Quadratic Knapsack Problem ⋮ 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 ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ Scheduling with two competing agents to minimize total weighted earliness ⋮ On the rectangular knapsack problem ⋮ Single machine scheduling with non-availability interval and optional job rejection ⋮ Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines ⋮ Minimizing total weighted completion time with an unexpected machine unavailable interval ⋮ A lifted-space dynamic programming algorithm for the quadratic knapsack problem ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Competitive two-agent scheduling with release dates and preemption on a single machine ⋮ Parallel machines scheduling with machine maintenance for minsum criteria ⋮ A Dynamic Programming Heuristic for the Quadratic Knapsack Problem ⋮ Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance ⋮ A strongly polynomial FPTAS for the symmetric quadratic knapsack problem ⋮ 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 ⋮ On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem ⋮ Single machine scheduling with semi-resumable machine availability constraints ⋮ Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time ⋮ Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time ⋮ Approximate and exact merging of knapsack constraints with cover inequalities ⋮ 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 ⋮ Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date ⋮ Solving 0-1 knapsack problems based on amoeboid organism algorithm ⋮ 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 \(r\)-weighted minimization knapsack problems ⋮ A PTAS for a class of binary non-linear programs with low-rank functions ⋮ Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product

Uses Software

• Knapsack

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

This page was built for publication: Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications