Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
From MaRDI portal
Publication:1651695
DOI10.1016/j.ejor.2018.04.013zbMath1403.90514OpenAlexW2796556323WikidataQ130037988 ScholiaQ130037988MaRDI QIDQ1651695
Nir Halman, Vitaly A. Strusevich, Hans Kellerer
Publication date: 12 July 2018
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2018.04.013
combinatorial optimizationFPTASgeometric rounding\(K\)-approximation sets and functionsnon-linear Boolean programming
Related Items
A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with nonlinear processing times, Bi-criteria path problem with minimum length and maximum survival probability, Strongly polynomial FPTASes for monotone dynamic programs, Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
Cites Work
- Unnamed Item
- Unnamed Item
- Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
- An FPTAS for optimizing a class of low-rank functions over a polytope
- A survey on offline scheduling with rejection
- A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
- An FPTAS for minimizing the product of two non-negative linear cost functions
- Differential approximation schemes for half-product related functions and their scheduling applications
- Approximability issues for unconstrained and constrained maximization of half-product related functions
- Analysis of bounds for a capacitated single-item lot-sizing problem
- 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
- A new fully polynomial time approximation scheme for the Knapsack problem
- An efficient fully polynomial approximation scheme for the Subset-Sum problem.
- Single-item dynamic lot-sizing problems: an updated survey
- Improved dynamic programming in connection with an FPTAS for the knapsack problem
- Positive half-products and scheduling with controllable processing times
- A nonlinear knapsack problem
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
- Complexity and algorithms for nonlinear optimization problems
- A single-item economic lot-sizing problem with a non-uniform resource: Approximation
- An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Minimization of Half-Products
- Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an Oracle
- A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
- MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK
- Fast Approximation Algorithms for Knapsack Problems
- Combinatorial Problems: Reductibility and Approximation
- Approximation Algorithms for Certain Scheduling Problems
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Parallel Machine Scheduling: Impact of Adding Extra Machines
- Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
