English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The minimum linear ordering problem (MLOP) generalizes well-knowncombinatorial optimization problems such as minimum linear arrangement andminimum sum set cover. MLOP seeks to minimize an aggregated cost $f(\cdot)$ dueto an ordering $\sigma$ of the items (say $[n]$), i.e., $\min_{\sigma}\sum_{i\in [n]} f(E_{i,\sigma})$, where $E_{i,\sigma}$ is the set of itemsmapped by $\sigma$ to indices $[i]$. Despite an extensive literature on MLOPvariants and approximations for these, it was unclear whether the graphicmatroid MLOP was NP-hard. We settle this question through non-trivialreductions from mininimum latency vertex cover and minimum sum vertex coverproblems. We further propose a new combinatorial algorithm for approximatingmonotone submodular MLOP, using the theory of principal partitions. This is incontrast to the rounding algorithm by Iwata, Tetali, and Tripathi [ITT2012],using Lov\'asz extension of submodular functions. We show a$(2-\frac{1+\ell_{f}}{1+|E|})$-approximation for monotone submodular MLOP where$\ell_{f}=\frac{f(E)}{\max_{x\in E}f(\{x\})}$ satisfies $1 \leq \ell_f \leq|E|$. Our theory provides new approximation bounds for special cases of theproblem, in particular a $(2-\frac{1+r(E)}{1+|E|})$-approximation for thematroid MLOP, where $f = r$ is the rank function of a matroid. We further showthat minimum latency vertex cover (MLVC) is $\frac{4}{3}$-approximable, bywhich we also lower bound the integrality gap of its natural LP relaxation,which might be of independent interest.

Hardness and Approximation of Submodular Minimum Linear Ordering Problems