The ACO Seminar (2021–2022)

A Minimum Linear Ordering Problem (MLOP) is an optimization over orderings/permutations of a finite set, given along with a non-negative (cost) function f, with the objective of minimizing the aggregated values of f over prefixes of the ordering. This is in contrast to the classical phenomenon of minimizing a cost function over combinatorial subsets, e.g., the minimum set cover versus the MLOP counterpart of minimum sum set cover, introduced by Feige, Lov ́asz, and Tetali in 2004. While the more general MLOP for supermodular cost functions is also 4 approximable [ITT 12] using a greedy algorithm that is further NP-hard to improve [FLT 04]; the approximability of submodular (cost function) MLOP remains less resolved. For the monotone submodular MLOP, we present a 2-(1+L)/(n+1) approximation, where L can be interpreted as a measure of linearity of f, using a different approach and refining upon the 2-2/(n+1) approximation by Iwata, Tetali, and Tripathi. We further show the problem remains NP-hard, even for the special case of f being the rank of a (graphic) matroid, and discuss connections to and open problems in the literature. This work is joint work with Swati Gupta, Shengding Sun, Prasad Tetali, and Michael Wigal.