Hardness and approximation of submodular minimum linear ordering problems

• 成果类型: Article
• 署名作者: Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C.
• 署名单位: University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02038-z
• 发表日期: 2024
• 页码: 277-318
• 关键词: vertex cover; set; algorithm; SUM; arrangement; complexity

摘要

The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost f (center dot) due to an ordering sigma of the items (say [n]), i.e., min(sigma) Sigma(i is an element of n]) f (E-i,E- sigma), where E-i,E- sigma is the set of items mapped by s to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovasz extension of submodular functions. We show a (2 - 1+l(f)/1+vertical bar E vertical bar)-approximation for monotone submodular MLOP where l(f) = f(E)/max(x is an element of E) f({x}) satisfies 1 <= = l(f) <= vertical bar E vertical bar. Our theory provides new approximation bounds for special cases of the problem, in particular a (2-1+r(E)/1+vertical bar E vertical bar)-approximation for the matroid MLOP, where f = r is the rank function of a matroid. We further show that minimum latency vertex cover is 4/3-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.