The symmetric quadratic knapsack problem: approximation and scheduling applications (Q1936656)

scientific article; zbMATH DE number 6134732

Language	Label	Description	Also known as
English	The symmetric quadratic knapsack problem: approximation and scheduling applications	scientific article; zbMATH DE number 6134732

Statements

instance of

scholarly article

0 references

title

The symmetric quadratic knapsack problem: approximation and scheduling applications (English)

0 references

0 references

0 references

0 references

6 February 2013

0 references

zbMATH Keywords

quadratic knapsack

0 references

half-product

0 references

single machine scheduling

0 references

FPTAS

0 references

MaRDI profile type

Publication

0 references

full work available at URL

https://doi.org/10.1007/s10288-011-0180-x

0 references

cites work

Single machine flow-time scheduling with a single breakdown

0 references

Scheduling Problems with Two Competing Agents

0 references

Minimization of half-products

0 references

Minimizing Mean Squared Deviation of Completion Times About a Common Due Date

0 references

Algorithms for the least distance problem

0 references

Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint

0 references

Quadratic resource allocation with generalized upper bounds

0 references

An O(n) algorithm for quadratic knapsack problems

0 references

Mimimization of agreeably weighted variance in single machine systems

0 references

A half-product based approximation scheme for agreeably weighted completion time variance

0 references

Note—A Note on the Minimization of Mean Squared Deviation of Completion Times About a Common Due Date

0 references

On the Minimization of Completion Time Variance with a Bicriteria Extension

0 references

Minimising Waiting Time Variance in the Single Machine Problem

0 references

Universal Sequencing on a Single Machine

0 references

FPTAS for half-products minimization with scheduling applications

0 references

Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation

0 references

Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date

0 references

Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date

0 references

Complexity and algorithms for convex network optimization and other nonlinear problems

0 references

Convex separable optimization is not much harder than linear optimization

0 references

New Lower and Upper Bounds for Scheduling Around a Small Common Due Date

0 references

Scheduling around a small common due date

0 references

Some comments on sequencing with controllable processing times

0 references

Positive half-products and scheduling with controllable processing times

0 references

Algorithms for minclique scheduling problems

0 references

Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date

0 references

Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period

0 references

Minimizing Variation of Flow Time in Single Machine Systems

0 references

An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates

0 references

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

0 references

An efficient fully polynomial approximation scheme for the Subset-Sum problem.

0 references

A new fully polynomial time approximation scheme for the Knapsack problem

0 references

Improved dynamic programming in connection with an FPTAS for the knapsack problem

0 references

Q4821303

0 references

Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance

0 references

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

0 references

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

0 references

MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK

0 references

Approximation algorithms for minimizing the total weighted tardiness on a single machine

0 references

A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem

0 references

Q3873927

0 references

Completion time variance minimization on a single machine is difficult

0 references

New results on the completion time variance minimization

0 references

Minimization of ordered, symmetric half-products

0 references

Fast fully polynomial approximation schemes for minimizing completion time variance

0 references

Two-machine flow shop no-wait scheduling with machine maintenance

0 references

Planning Machine Maintenance in Two-Machine Shop Scheduling

0 references

Minimizing the makespan in a single machine scheduling problem with a time-based learning effect

0 references

A Functional Equation and its Application to Resource Allocation and Sequencing Problems

0 references

Machine scheduling with an availability constraint

0 references

Q3993418

0 references

Variance Minimization in Single Machine Sequencing Problems

0 references

Interior path following primal-dual algorithms. II: Convex quadratic programming

0 references

On the solution of concave knapsack problems

0 references

A survey of results for sequencing problems with controllable processing times

0 references

The quadratic knapsack problem -- a survey

0 references

The quadratic 0-1 knapsack problem with series-parallel support

0 references

On a nonseparable convex maximization problem with continuous Knapsack constraints

0 references

An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints

0 references

Algorithms for Scheduling Independent Tasks

0 references

A survey of scheduling with controllable processing times

0 references

Single machine scheduling with controllable release and processing parameters

0 references

Convex quadratic and semidefinite programming relaxations in scheduling

0 references

A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks

0 references

Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.

0 references

Preemptive scheduling with availability constraints to minimize total weighted completion times

0 references

An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine

0 references

Q4034337

0 references

Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan

0 references

Identifiers

zbMATH Open document ID

1264.90001

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

10.1007/S10288-011-0180-X

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1936656