Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint

DOI10.1007/S10288-022-00509-1MaRDI QIDQ6097849zbMATH OpenFDO

Authors Nir Halman, M. Y. Kovalyov, Alain Quilliot

Publication date 7 June 2023

Published in 4OR (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10288-022-00509-1

zbMATH Keywords

FPTASknapsack problemsparametric optimizationpolynomial algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Sensitivity, stability, parametric optimization (90C31) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• The inverse-parametric knapsack problem
• A linear-time algorithm for solving continuous maximin knapsack problems
• Continuous maximin knapsack problems with GLB constraints
• Approximation schemes for the parametric knapsack problem
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications

Cites work

• A fast parametric assignment algorithm with applications in max-algebra
• A Fast Parametric Maximum Flow Algorithm and Applications
• A lower bound for the shortest path problem
• A note on the parametric maximum flow problem and some related reoptimization issues
• An approximation algorithm for a general class of parametric optimization problems
• An FPTAS for the knapsack problem with parametric weights
• An FPTAS for the parametric knapsack problem
• Approximation schemes for the parametric knapsack problem
• Combinatorial Optimization with Rational Objective Functions
• Complexity of some parametric integer and network programming problems
• Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh
• Computational complexity of parametric linear programming
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• Faster parametric shortest path and minimum‐balance algorithms
• Generalization of a theorem on the parametric maximum flow problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Nonlinear one-parametric bottleneck linear programming
• Parametric shortest path algorithms with an application to cyclic staffing
• Parametric Solution for Linear Bicriteria Knapsack Models
• Using sparsification for parametric minimum spanning tree problems

Cited in

(6)

• A special class parametric of knapsack problems: Analytic aids and heuristics
• Hybrid approaches for the two-scenario max-min knapsack problem
• Continuous maximin knapsack problems with GLB constraints
• The knapsack problem with a minimum filling constraint
• Minmax linear knapsack problem with grouped variables and gub
• Study of the linear parametrization of criteria in the bicriteria knapsack problem

This page was built for publication: Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint

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