Approximability issues for unconstrained and constrained maximization of half-product related functions

DOI10.1016/J.TCS.2016.11.009MaRDI QIDQ730001zbMATH OpenOpenAlexFDO

Authors Hans Kellerer, Rebecca Sarto Basso, V. A. Strusevich

Publication date 23 December 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.11.009

zbMATH Keywords

FPTAShalf-productnon-approximabilityquadratic knapsack

Mathematics Subject Classification ID

Boolean programming (90C09) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Differential approximation schemes for half-product related functions and their scheduling applications
• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• Minimization of half-products
• FPTAS for half-products minimization with scheduling applications

Cites work

• A Selection Problem of Shared Fixed Costs and Network Flows
• An analysis of approximations for maximizing submodular set functions—I
• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• FPTAS for half-products minimization with scheduling applications
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• Improved Algorithms for Bipartite Network Flow
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Minimization of half-products
• Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
• On the supermodular knapsack problem
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Pseudo-Boolean optimization
• The quadratic 0-1 knapsack problem with series-parallel support
• The symmetric quadratic knapsack problem: approximation and scheduling applications

Cited in

(4)

• Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Minimization of half-products
• Differential approximation schemes for half-product related functions and their scheduling applications

This page was built for publication: Approximability issues for unconstrained and constrained maximization of half-product related functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730001)