Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints

DOI10.1016/J.EJOR.2018.04.013MaRDI QIDQ1651695zbMATH OpenOpenAlexWikidataFDO

Authors Nir Halman, Hans Kellerer, V. A. Strusevich

Publication date 12 July 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ejor.2018.04.013

zbMATH Keywords

combinatorial optimizationFPTASgeometric rounding\(K\)-approximation sets and functionsnon-linear Boolean programming

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Nonlinear programming (90C30) Boolean programming (90C09)

Recommendations

• Approximating single- and multi-objective nonlinear sum and product knapsack problems
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• On a discrete nonlinear and nonseparable knapsack problem
• An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints
• A unified method for a class of convex separable nonlinear knapsack problems
• A Solution Strategy for a Class of Nonlinear Knapsack Problems
• Approximation schemes for multiperiod binary knapsack problems
• Approximation schemes for the parametric knapsack problem
• Nonconvex piecewise linear knapsack problems

Cites work

• scientific article; zbMATH DE number 988191 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A fully polynomial-time approximation scheme for single-item stochastic inventory control with discrete demand
• A new fully polynomial time approximation scheme for the Knapsack problem
• A nonlinear knapsack problem
• A single-item economic lot-sizing problem with a non-uniform resource: Approximation
• A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
• A survey on offline scheduling with rejection
• About strongly polynomial time algorithms for quadratic optimization over submodular constraints
• An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure
• An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
• An FPTAS for minimizing the product of two non-negative linear cost functions
• An FPTAS for optimizing a class of low-rank functions over a polytope
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Analysis of bounds for a capacitated single-item lot-sizing problem
• Approximability issues for unconstrained and constrained maximization of half-product related functions
• Approximating the nonlinear newsvendor and single-item stochastic lot-sizing problems when data is given by an oracle
• Approximation Algorithms for Certain Scheduling Problems
• Combinatorial Problems: Reductibility and Approximation
• Complexity and algorithms for nonlinear optimization problems
• Differential approximation schemes for half-product related functions and their scheduling applications
• FPTAS for half-products minimization with scheduling applications
• Fast Approximation Algorithms for Knapsack Problems
• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Fully polynomial time approximation schemes for stochastic dynamic programs
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Minimization of half-products
• Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Parallel Machine Scheduling: Impact of Adding Extra Machines
• Positive half-products and scheduling with controllable processing times
• Quadratic programming and combinatorial minimum weight product problems
• Single-item dynamic lot-sizing problems: an updated survey
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(6)

• Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
• Theory and methodology of time-dependent scheduling: past, present and future
• Strongly polynomial FPTASes for monotone dynamic programs
• Two new approximation schemes for maximizing the weighted number of just-in-time jobs in a multi-machine proportionate flow shop
• 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

This page was built for publication: Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints

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