Approximation schemes for the parametric knapsack problem

DOI10.1016/J.IPL.2016.12.003zbMath1401.90190OpenAlexW2563945941MaRDI QIDQ506160

Clemens Thielen, Pascal Halffmann, Alberto Giudici, Stefan Ruzika

Publication date: 31 January 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.12.003

zbMATH Keywords

approximation algorithmsbicriteria optimization problemsparametric optimization problems

Mathematics Subject Classification ID

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

Related Items (11)

An FPTAS for the parametric knapsack problem ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ An approximation algorithm for a general class of parametric optimization problems ⋮ Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint ⋮ On approximating the incremental knapsack problem ⋮ Approximating the 3-period incremental knapsack problem ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ The binary knapsack problem with qualitative levels ⋮ An FPTAS for the knapsack problem with parametric weights ⋮ An approximation algorithm for a general class of multi-parametric optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parametric mixed-integer 0-1 linear programming: The general case for a single parameter
• Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
• Parametric shortest path algorithms with an application to cyclic staffing
• Generalization of a theorem on the parametric maximum flow problem
• The inverse-parametric knapsack problem
• Reporting and counting segment intersections
• A note on the parametric maximum flow problem and some related reoptimization issues
• Approximating Multiobjective Knapsack Problems
• Complexity of some parametric integer and network programming problems
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Approximate Algorithms for the 0/1 Knapsack Problem
• Parametric Solution for Linear Bicriteria Knapsack Models
• A Fast Parametric Maximum Flow Algorithm and Applications
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• Faster parametric shortest path and minimum‐balance algorithms
• A lower bound for the shortest path problem

This page was built for publication: Approximation schemes for the parametric knapsack problem