Georgia Institute of Technology College of Sciences

The minimum linear ordering problem (MLOP) asks to minimize the aggregated cost of a set function f with respect to some ordering \sigma of the base set. That is, MLOP asks to find a permutation \sigma that minimizes the sum \sum_{i = 1}^{|E|}f({e \in E : \sigma(e) \le i}). Many instances of MLOP have been studied in the literature, for example, minimum linear arrangement (MLA) or minimum sum vertex cover (MSVC). We will cover how graphic matroid MLOP, i.e. where f is taken to be the rank function of a graphic matroid, is NP-hard. This is achieved through a series of reductions beginning with MSVC. During these reductions, we will introduce a new problem, minimum latency vertex cover (MLVC) which we will also show has a 4/3 approximation. Finally, using the theory of principal partitions, we will show MLOP with monotone submodular function f : E \to \mathbb{R}^+ has a 2 - (1 + \ell_f)/(1 + |E|) approximation where \ell_f = f(E)/(\max_{x \in E}f({x})). As a corollary, we obtain a 2 - (1 + r(E))/(1 + |E|) approximation for matroid MLOP where r is the rank function of the matroid. We will also end with some interesting open questions.

Joint work with Majid Farhadi, Swati Gupta, Shengding Sun, and Prasad Tetali.