Differential approximation schemes for half-product related functions and their scheduling applications
type: Item
instance of: scholarly article
title: Differential approximation schemes for half-product related functions and their scheduling applications
zbMATH Open document ID: 1352.90063
author: Rebecca Sarto Basso
author: V. A. Strusevich
published in: Discrete Applied Mathematics
publication date: 2016-12-22T00:00:00Z
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6668152
zbMATH Keywords: half-product
zbMATH Keywords: quadratic knapsack
zbMATH Keywords: FPTAS
zbMATH Keywords: differential approximation schemes
MaRDI profile type: Publication
full work available at URL: j.dam.2015.10.006
OpenAlex ID: W2245987882
cites work: Mathematical Foundations of Computer Science 2003
cites work: Handbook of Approximation Algorithms and Metaheuristics
cites work: Minimization of half-products
cites work: Pseudo-Boolean optimization
cites work: On an approximation measure founded on the links between optimization and polynomial approximation theory
cites work: FPTAS for half-products minimization with scheduling applications
cites work: Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
cites work: An FPTAS for minimizing the product of two non-negative linear cost functions
cites work: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
cites work: Positive half-products and scheduling with controllable processing times
cites work: Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability
cites work: Reducibility among Combinatorial Problems
cites work: Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
cites work: Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
cites work: MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK
cites work: The symmetric quadratic knapsack problem: approximation and scheduling applications
cites work: Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
cites work: Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
cites work: Quadratic programming and combinatorial minimum weight product problems
cites work: Minimization of ordered, symmetric half-products
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: An analysis of approximations for maximizing submodular set functions—I
cites work: A Selection Problem of Shared Fixed Costs and Network Flows
cites work: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
cites work: When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
cites work: A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
DOI: 10.1016/J.DAM.2015.10.006
description: scientific article; zbMATH DE number 6668152