Differential approximation schemes for half-product related functions and their scheduling applications
From MaRDI portal
Publication:729806
DOI10.1016/j.dam.2015.10.006zbMath1352.90063OpenAlexW2245987882MaRDI QIDQ729806
Rebecca Sarto Basso, Vitaly A. Strusevich
Publication date: 22 December 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.10.006
Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09)
Related Items
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
Cites Work
- 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
- An FPTAS for minimizing the product of two non-negative linear cost functions
- Pseudo-Boolean optimization
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- Quadratic programming and combinatorial minimum weight product problems
- 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
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Minimization of ordered, symmetric half-products
- Positive half-products and scheduling with controllable processing times
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- 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
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Minimization of Half-Products
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Handbook of Approximation Algorithms and Metaheuristics
- MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Reducibility among Combinatorial Problems
- Mathematical Foundations of Computer Science 2003
- A Selection Problem of Shared Fixed Costs and Network Flows
- Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
