Note on combinatorial optimization with max-linear objective functions

DOI10.1016/0166-218X(93)90043-NzbMath0777.90046OpenAlexW2098120964MaRDI QIDQ1803670

Francesco Maffioli, Sung-Jin Chung, Horst W. Hamacher, Katta G. Murty

Publication date: 29 June 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90043-n

zbMATH Keywords

branch-and-boundlower boundsmulticriteria optimizationstrongly NP-hardmax-linear combinatorial problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach, On spanning tree problems with multiple objectives, A discussion of scalarization techniques for multiple objective integer programming, A note on \(K\) best network flows, Unnamed Item, A Benders decomposition approach to product location in carousel storage systems, Three algorithms for bicriteria integer linear programs, Multicriteria planar location problems, Geometric methods to solve max-ordering location problems

Cites Work

• The matroidal knapsack: A class of (often) well-solvable problems
• Multi-constrained matroidal knapsack problems
• An approach to nonlinear programming
• A new exchange property for matroids and its application to max-min-problems
• Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems
• Complexity of some parametric integer and network programming problems
• Some NP-complete problems in quadratic and nonlinear programming
• Algorithms for flows with parametric capacities
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item