Note on combinatorial optimization with max-linear objective functions

Abstract

We consider combinatorial optimization problems with a feasible solution set S[subset of or equal to]{0,1}n specified by a system of linear constraints in 0-1 variables. Additionally, several cost functions c1,...,cp are given. The max-linear objective function is defined by f(x):=max{c1x,...,cpx: x[set membership, variant]S}; where cq:=(cq1,...,cqn) is for q=1,...,p an integer row vector in n.The problem of minimizing f(x) over S is called the max-linear combinatorial optimization (MLCO) problem.We will show that MLCO is NP-hard even for the simplest case of S[subset of or equal to]{0,1}n and p=2, and strongly NP-hard for general p. We discuss the relation to multi-criteria optimization and develop some bounds for MLCO.