The symmetric quadratic knapsack problem: approximation and scheduling applications
From MaRDI portal
Publication:1936656
DOI10.1007/s10288-011-0180-xzbMath1264.90001OpenAlexW1973197094MaRDI QIDQ1936656
Hans Kellerer, Vitaly A. Strusevich
Publication date: 6 February 2013
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10288-011-0180-x
Quadratic programming (90C20) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items
Twelve surveys in operations research, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, 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, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Single machine scheduling with a generalized job-dependent cumulative effect, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, Surveys in operations research, 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, Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A half-product based approximation scheme for agreeably weighted completion time variance
- Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
- An O(n) algorithm for quadratic knapsack problems
- Complexity and algorithms for convex network optimization and other nonlinear problems
- Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation
- A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
- The quadratic knapsack problem -- a survey
- A survey of results for sequencing problems with controllable processing times
- Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- FPTAS for half-products minimization with scheduling applications
- Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
- Minimizing the makespan in a single machine scheduling problem with a time-based learning effect
- Single machine flow-time scheduling with a single breakdown
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- Mimimization of agreeably weighted variance in single machine systems
- Scheduling around a small common due date
- A new fully polynomial time approximation scheme for the Knapsack problem
- Completion time variance minimization on a single machine is difficult
- Quadratic resource allocation with generalized upper bounds
- An efficient fully polynomial approximation scheme for the Subset-Sum problem.
- Some comments on sequencing with controllable processing times
- Fast fully polynomial approximation schemes for minimizing completion time variance
- Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.
- Minimization of ordered, symmetric half-products
- Improved dynamic programming in connection with an FPTAS for the knapsack problem
- 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
- The quadratic 0-1 knapsack problem with series-parallel support
- An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
- On the solution of concave knapsack problems
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- Approximation algorithms for minimizing the total weighted tardiness on a single machine
- Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
- A survey of scheduling with controllable processing times
- Single machine scheduling with controllable release and processing parameters
- Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance
- Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
- Two-machine flow shop no-wait scheduling with machine maintenance
- Machine scheduling with an availability constraint
- On a nonseparable convex maximization problem with continuous Knapsack constraints
- Minimization of Half-Products
- Convex quadratic and semidefinite programming relaxations in scheduling
- Planning Machine Maintenance in Two-Machine Shop Scheduling
- MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK
- Universal Sequencing on a Single Machine
- Scheduling Problems with Two Competing Agents
- Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
- Minimizing Variation of Flow Time in Single Machine Systems
- Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
- Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
- On the Minimization of Completion Time Variance with a Bicriteria Extension
- Algorithms for Scheduling Independent Tasks
- Minimising Waiting Time Variance in the Single Machine Problem
- New Lower and Upper Bounds for Scheduling Around a Small Common Due Date
- An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine
- Note—A Note on the Minimization of Mean Squared Deviation of Completion Times About a Common Due Date
- A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
- An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
- Variance Minimization in Single Machine Sequencing Problems
- Convex separable optimization is not much harder than linear optimization
- Algorithms for minclique scheduling problems
