FPTAS for half-products minimization with scheduling applications
From MaRDI portal
Publication:1005250
DOI10.1016/j.dam.2008.01.018zbMath1155.90379OpenAlexW2140465779MaRDI QIDQ1005250
Publication date: 9 March 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.01.018
Related Items (13)
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 ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Single machine scheduling with a generalized job-dependent cumulative effect ⋮ Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance ⋮ Scheduling with common due date assignment to minimize generalized weighted earliness-tardiness penalties ⋮ Minimizing weighted mean absolute deviation of job completion times from their weighted mean ⋮ On the complexity of the single machine scheduling problem minimizing total weighted delay penalty ⋮ 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 ⋮ 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
Cites Work
- A half-product based approximation scheme for agreeably weighted completion time variance
- Fast approximation algorithm for job sequencing with deadlines
- Fast fully polynomial approximation schemes for minimizing completion time variance
- Minimization of ordered, symmetric half-products
- Positive half-products and scheduling with controllable processing times
- New results on the completion time variance minimization
- Improving the complexities of approximation algorithms for optimization problems
- Single machine scheduling with controllable release and processing parameters
- Minimization of Half-Products
- Algorithms for Scheduling Independent Tasks
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine
- A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
- Algorithms for minclique scheduling problems
This page was built for publication: FPTAS for half-products minimization with scheduling applications
