The symmetric quadratic knapsack problem: approximation and scheduling applications
From MaRDI portal
Publication:1936656
Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Boolean programming (90C09)
Recommendations
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
- FPTAS for half-products minimization with scheduling applications
Cites work
- scientific article; zbMATH DE number 3677572 (Why is no real title available?)
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 167292 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
- A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
- A half-product based approximation scheme for agreeably weighted completion time variance
- A new fully polynomial time approximation scheme for the Knapsack problem
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- A survey of results for sequencing problems with controllable processing times
- A survey of scheduling with controllable processing times
- Algorithms for Scheduling Independent Tasks
- Algorithms for minclique scheduling problems
- Algorithms for the least distance problem
- An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine
- An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
- An O(n) algorithm for quadratic knapsack problems
- An efficient fully polynomial approximation scheme for the Subset-Sum problem.
- An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
- Approximation algorithms for minimizing the total weighted tardiness on a single machine
- Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance
- Completion time variance minimization on a single machine is difficult
- Complexity and algorithms for convex network optimization and other nonlinear problems
- Convex quadratic and semidefinite programming relaxations in scheduling
- Convex separable optimization is not much harder than linear optimization
- 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
- FPTAS for half-products minimization with scheduling applications
- Fast fully polynomial approximation schemes for minimizing completion time variance
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
- Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
- Improved dynamic programming in connection with an FPTAS for the knapsack problem
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- Machine scheduling with an availability constraint
- Mimimization of agreeably weighted variance in single machine systems
- Minimising Waiting Time Variance in the Single Machine Problem
- Minimization of half-products
- Minimization of ordered, symmetric half-products
- Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
- Minimizing Variation of Flow Time in Single Machine Systems
- Minimizing the makespan in a single machine scheduling problem with a time-based learning effect
- Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
- New Lower and Upper Bounds for Scheduling Around a Small Common Due Date
- New results on the completion time variance minimization
- Note—A Note on the Minimization of Mean Squared Deviation of Completion Times About a Common Due Date
- On a nonseparable convex maximization problem with continuous Knapsack constraints
- On the Minimization of Completion Time Variance with a Bicriteria Extension
- On the solution of concave knapsack problems
- Planning Machine Maintenance in Two-Machine Shop Scheduling
- Positive half-products and scheduling with controllable processing times
- Preemptive scheduling with availability constraints to minimize total weighted completion times
- Quadratic resource allocation with generalized upper bounds
- Scheduling Problems with Two Competing Agents
- Scheduling around a small common due date
- Single machine flow-time scheduling with a single breakdown
- Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation
- Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.
- Single machine scheduling with controllable release and processing parameters
- Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan
- Some comments on sequencing with controllable processing times
- The quadratic 0-1 knapsack problem with series-parallel support
- The quadratic knapsack problem -- a survey
- Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
- Two-machine flow shop no-wait scheduling with machine maintenance
- Universal sequencing on a single machine
- Variance Minimization in Single Machine Sequencing Problems
- Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
Cited in
(18)- Approximation schemes for \(r\)-weighted minimization knapsack problems
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- A PTAS for a class of binary non-linear programs with low-rank functions
- Surveys in operations research
- Twelve surveys in operations research
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
- Approximation of the quadratic knapsack problem
- 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
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- 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
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- Single machine scheduling with a generalized job-dependent cumulative effect
- A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
This page was built for publication: The symmetric quadratic knapsack problem: approximation and scheduling applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1936656)
