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