Knapsack problems with position-dependent item weights or profits
Stanisław Gawiejnowicz, Nir Halman, Hans Kellerer
Abstract
Abstract We consider three new knapsack problems with variable weights or profits of items, where the weight or profit of an item depends on the position of the item in the sequence of items packed in the knapsack. We show how to solve the problems exactly using dynamic programming algorithms with pseudo-polynomial running times and propose fully polynomial-time approximation schemes for their approximate solution.
Topics & Concepts
Knapsack problemContinuous knapsack problemTheory of computationPolynomial-time approximation schemeMathematical optimizationMathematicsSequence (biology)Position (finance)Dynamic programmingChange-making problemVariable (mathematics)Generalized assignment problemComputer scienceAlgorithmOptimization problemEconomicsBiologyGeneticsFinanceMathematical analysisOptimization and Packing ProblemsAdvanced Manufacturing and Logistics OptimizationScheduling and Optimization Algorithms