Approximability issues for unconstrained and constrained maximization of half-product related functions
From MaRDI portal
Publication:730001
DOI10.1016/j.tcs.2016.11.009zbMath1356.90084OpenAlexW2554630409MaRDI QIDQ730001
Rebecca Sarto Basso, Hans Kellerer, Vitaly 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
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
- Unnamed Item
- Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
- Pseudo-Boolean optimization
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- FPTAS for half-products minimization with scheduling applications
- On the supermodular knapsack problem
- The quadratic 0-1 knapsack problem with series-parallel support
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Minimization of Half-Products
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- 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
- Improved Algorithms for Bipartite Network Flow
- A Selection Problem of Shared Fixed Costs and Network Flows
