Note on combinatorial optimization with max-linear objective functions

The authors consider combinatorial optimization problems with a feasible solution set specified by a system of linear constraints in 0-1 variables. Additionally, several cost functions are given. The max-linear objective function is defined by where is for an integer row vector in . The problem of over S is called the max-linear combinatorial optimization (MLCO) problem. The authors will show that MLCO is NP-hard even for the simplest case of and , and strongly NP-hard for general p. They discuss the relation to multi-criteria optimization and develop some bounds for MLCO.