Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications (Q2630817)

scientific article

Language	Label	Description	Also known as
English	Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications	scientific article

Statements

instance of

scholarly article

0 references

title

Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications (English)

0 references

0 references

0 references

Annals of Operations Research

0 references

publication date

22 July 2016

0 references

zbMATH Keywords

quadratic knapsack

0 references

half-product

0 references

single machine scheduling

0 references

fptas

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s10479-015-2018-y

0 references

cites work

Single machine flow-time scheduling with a single breakdown

0 references

Scheduling Problems with Two Competing Agents

0 references

Mathematical Foundations of Computer Science 2003

0 references

Minimization of Half-Products

0 references

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

0 references

Q2743973

0 references

Pseudo-Boolean optimization

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

Q3988807

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

On an approximation measure founded on the links between optimization and polynomial approximation theory

0 references

Minimising Waiting Time Variance in the Single Machine Problem

0 references

Techniques for scheduling with rejection

0 references

Universal Sequencing on a Single Machine

0 references

FPTAS for half-products minimization with scheduling applications

0 references

Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions

0 references

On the supermodular knapsack problem

0 references

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

0 references

Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem

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

Complexity and algorithms for nonlinear optimization 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

A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions

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

Q3109947

0 references

Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability

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

Q4821303

0 references

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

0 references

Approximability issues for unconstrained and constrained maximization of half-product related functions

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

The symmetric quadratic knapsack problem: approximation and scheduling applications

0 references

Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product

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

Single machine flow-time scheduling with scheduled maintenance

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

An analysis of approximations for maximizing submodular set functions—I

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

A Selection Problem of Shared Fixed Costs and Network Flows

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

Differential approximation schemes for half-product related functions and their scheduling applications

0 references

A combinatorial algorithm minimizing submodular functions in strongly polynomial time.

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

A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

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

When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

0 references

Q4040221

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

1342.90064

0 references

DOI

10.1007/s10479-015-2018-y

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2630817