Approximation schemes for \(r\)-weighted minimization knapsack problems

DOI10.1007/s10479-018-3111-9zbMath1435.90120OpenAlexW2905351269WikidataQ128812425 ScholiaQ128812425MaRDI QIDQ2288864

Trung Thanh Nguyen, Areg Karapetyan, Khaled M. Elbassioni

Publication date: 20 January 2020

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-018-3111-9

zbMATH Keywords

polynomial-time approximation schemesmart gridpower generation planningeconomic dispatch controlquasi polynomial-time approximation schemeweighted minimization knapsack

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (4)

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Approximating single- and multi-objective nonlinear sum and product knapsack problems ⋮ A PTAS for a class of binary non-linear programs with low-rank functions

Uses Software

• APMonitor

Cites Work

• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Approximate algorithms for some generalized knapsack problems
• The nonlinear knapsack problem - algorithms and applications
• Complex-demand scheduling problem with application in smart grid
• The quadratic 0-1 knapsack problem with series-parallel support
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• New results on quantifier elimination over real closed fields and applications to constraint databases
• Approximating the Quadratic Knapsack Problem on Special Graph Classes
• On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation schemes for \(r\)-weighted minimization knapsack problems