Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
From MaRDI portal
Publication:257209
DOI10.1016/j.ejor.2012.12.028zbMath1332.90168OpenAlexW2032733538MaRDI QIDQ257209
Hans Kellerer, Vitaly A. Strusevich
Publication date: 15 March 2016
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: http://gala.gre.ac.uk/id/eprint/10124/1/10124_STRUSEVICH_EJOR__%28AAM%29_%282013%29.pdf
schedulingscheduling with controllable processing timesFPTAShalf-productquadratic knapsackscheduling with rejection
Related Items
Two-machine open-shop scheduling with rejection to minimize the makespan, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, 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, Unrelated parallel machine scheduling problem with special controllable processing times and setups, Algorithms for communication scheduling in data gathering network with data compression, Order acceptance and scheduling with machine availability constraints, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, Communication scheduling in data gathering networks of heterogeneous sensors with data compression: algorithms and empirical experiments, Differential approximation schemes for half-product related functions and their scheduling applications, Approximability issues for unconstrained and constrained maximization of half-product related functions, Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
- 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
- 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
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem
- 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
- Techniques for scheduling with rejection
- Algorithms for minclique scheduling problems
