Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
From MaRDI portal
Publication:2630817
DOI10.1007/s10479-015-2018-yzbMath1342.90064OpenAlexW1736329744WikidataQ59475679 ScholiaQ59475679MaRDI QIDQ2630817
Vitaly A. Strusevich, Hans Kellerer
Publication date: 22 July 2016
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-015-2018-y
Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09)
Related Items
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 algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Single machine scheduling with non-availability interval and optional job rejection, Single machine scheduling with a generalized job-dependent cumulative effect, Scheduling with common due date assignment to minimize generalized weighted earliness-tardiness penalties, Differential approximation schemes for half-product related functions and their scheduling applications, Approximability issues for unconstrained and constrained maximization of half-product related functions, Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Pseudo-Boolean optimization
- 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
- Differential approximation schemes for half-product related functions and their scheduling applications
- Approximability issues for unconstrained and constrained maximization of half-product related functions
- An O(n) algorithm for quadratic knapsack problems
- Single machine flow-time scheduling with scheduled maintenance
- 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
- Completion time variance minimization on a single machine is difficult
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- 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
- 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
- On the supermodular knapsack problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- 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
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability
- Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem
- 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
- Complexity and algorithms for nonlinear optimization problems
- 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
- An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- 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
- An analysis of approximations for maximizing submodular set functions—I
- New Lower and Upper Bounds for Scheduling Around a Small Common Due Date
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- 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
- Techniques for scheduling with rejection
- A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
- Mathematical Foundations of Computer Science 2003
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
- A Selection Problem of Shared Fixed Costs and Network Flows
- Variance Minimization in Single Machine Sequencing Problems
- Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
- Convex separable optimization is not much harder than linear optimization
- Algorithms for minclique scheduling problems
