Access the full text.
Sign up today, get DeepDyve free for 14 days.
Loading next page...
/lp/springer-journals/max-max-max-min-min-max-and-min-min-knapsack-problems-with-a-MtW8JsdH23
References (27)
-
I. Schubert, U. Zimmermann (1985)
One-parametric bottleneck transportation problemsAnnals of Operations Research, 4
-
N. Megiddo (1978)
Combinatorial optimization with rational objective functionsProceedings of the tenth annual ACM symposium on Theory of computing
-
C. Bazgan, Arne Herzel, Stefan Ruzika, Clemens Thielen, D. Vanderpooten (2020)
An approximation algorithm for a general class of parametric optimization problemsJournal of Combinatorial Optimization, 43
-
M. Scutellá (2007)
A note on the parametric maximum flow problem and some related reoptimization issuesAnnals of Operations Research, 150
-
N. Young, R. Tarjan, J. Orlin (1991)
Faster parametric shortest path and minimum-balance algorithmsNetworks, 21
-
A. Giudici, Pascal Halffmann, Stefan Ruzika, Clemens Thielen (2017)
Approximation schemes for the parametric knapsack problemInf. Process. Lett., 120
-
AnFPTAS for the knapsack problemwith parametricweights -
K Mulmuley, P Shah (2001)
A lower bound for the shortest path problemJ Comput Syst Sci, 63
-
Patricia Carstensen (1983)
Complexity of some parametric integer and network programming problemsMathematical Programming, 26
-
G. Gallo, M. Grigoriadis, R. Tarjan (1989)
A Fast Parametric Maximum Flow Algorithm and ApplicationsSIAM J. Comput., 18
-
K. Murty (1980)
Computational complexity of parametric linear programmingMathematical Programming, 19
-
G. Ruhe (1988)
Complexity results for multicriterial and parametric network flows using a pathological graph of ZadehZeitschrift für Operations Research, 32
-
U. Zimmermann, I. Schubert (1985)
Nonlinear one-parametric bottleneck linear programmingZeitschrift für Operations Research, 29
-
N Megiddo (1979)
Combinatorial optimization with rational objective functionsMath Oper Res, 4
-
Elisabeth Gassner, Bettina Klinz (2010)
A fast parametric assignment algorithm with applications in max‐algebraNetworks, 55
-
Patricia Carstensen (1983)
The complexity of some problems in parametric linear and combinatorial programming -
David Johnson, W. Freeman
The Np-completeness Column: an Ongoing Guide Garey and Myself in Our Book ''computers and Intractability: a Guide to the Theory of Np-completeness,'' -
Michael Holzhauser, S. Krumke (2017)
An FPTAS for the parametric knapsack problemArXiv, abs/1701.07822
-
T. Gal (1994)
Postoptimal Analyses, Parametric Programming, and Related Topics: Degeneracy, Multicriteria Decision Making, Redundancy -
David Fernández-Baca, G. Slutzki, D. Eppstein (1996)
Using Sparsification for Parametric Minimum Spanning Tree Problems -
P. Agarwal, D. Eppstein, L. Guibas, M. Henzinger (1998)
Parametric and kinetic minimum spanning treesProceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)
-
J. Yates, W. Orlikowski, Kazuo Okamura, S. McCormick (1996)
Fast algorithms for parametric scheduling come from extensions to parametric maximum flowOper. Res., 47
-
M. Eben-Chaime (1996)
Parametric solution for linear bicriteria knapsack modelsManagement Science, 42
-
R. Karp, J. Orlin (1981)
Parametric shortest path algorithms with an application to cyclic staffingDiscret. Appl. Math., 3
-
K. Mulmuley, P. Shah (2000)
A lower bound for the shortest path problemProceedings 15th Annual IEEE Conference on Computational Complexity
-
T Arai, S Ueno, Y Kajitani (1993)
Generalization of a theorem on the parametric maximum flow problemDiscret Appl Math, 41
-
Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations
- Publisher
- Springer Journals
- Copyright
- Copyright © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2022
- ISSN
- 1619-4500
- eISSN
- 1614-2411
- DOI
- 10.1007/s10288-022-00509-1
- Publisher site
- See Article on Publisher Site
Abstract
Max–max, max–min, min–max and min–min optimization problems with a knapsack-type constraint containing a single numerical parameter are studied. The goal is to present optimal solutions for all possible values of the parameter. Algorithms with O(nlogn)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n\log n)$$\end{document} and O(n2)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^2)$$\end{document} running times are proposed for the problems with a fixed parameter and for the general problem, respectively, where n is the number of items to be packed into the knapsack. The latter algorithm determines optimal solution values for all values of the parameter in O(nlog2n)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n\log ^2 n)$$\end{document} time. The problem of deciding whether there exists a single optimal solution for all values of the numerical parameter is proved to be NP-complete.
Journal
4OR – Springer Journals
Published: Jun 1, 2023
Keywords: Knapsack problems; Parametric optimization; Polynomial algorithm; FPTAS; 90C31; 68Q25; 68Q17; 90C59