Note on combinatorial optimization with max-linear objective functions (Q1803670)

The authors consider the problem (MLCO) of minimizing \(f(x)=\max\{c^ 1x,\dots,c^ p x: x\in S\}\), where \(c^ q\) for \(q=1,\dots,p\) is a given row vector in \(\mathbb{R}^ n\) and \(S\subseteq\{0,1\}^ n\). They suppose the set \(S\) always has a special structure so that a single linear objective function can be optimized over it in polynomial time. In the paper it is proved that MLCO is NP-hard even for the simplest case of \(S=\{0,1\}^ n\) and \(p=2\), and strongly NP-hard for general \(p\). The relation of MLCO problem to multicriteria optimization (MCO) problems is presented by the following theorem: ``For any instance of MLCO problem there is an optimum solution which is efficient with respect to the cost function of MCO problem''. In the last section of the paper some lower bounds for the branch-and-bound method are presented. Overall, the paper is written in a clear style and is easily readable.