The symmetric quadratic knapsack problem: approximation and scheduling applications
From MaRDI portal
Publication:1936656
DOI10.1007/s10288-011-0180-xzbMath1264.90001MaRDI 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
90C20: Quadratic programming
90B35: Deterministic scheduling theory in operations research
90C59: Approximation methods and heuristics in mathematical programming
90C09: Boolean programming
90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
Related Items
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, 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, Single machine scheduling with a generalized job-dependent cumulative effect, Surveys in operations research, A PTAS for a class of binary non-linear programs with low-rank functions, 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 schemes for \(r\)-weighted minimization knapsack problems, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, Twelve surveys in operations research, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Approximation of the Quadratic Knapsack Problem
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
