The lexicographic multi-objective optimization problem (r-LMOP) with r (sum or bottleneck) objectives optimizes a first objective, then as far as a choice remains, a second one, then a third one and so on. A general solution scheme from literature is based on scaling; for the case that only sum criteria are involved the complexity is O(rlogn)T(n,m) with T(n,m) the complexity of optimization on combinatorial (sum) problem instances with m arcs and n nodes. For cases with at least one bottleneck criterion the complexity is at least O(rnlog 2n)T(n,m). We describe a solution scheme that is suited to solve the shortest path r-LMOP, the minimum spanning tree r-LMOP and the linear assignment r-LMOP; the complexity is in all cases O(r)T(n,m).
