2026-09-08T01:22:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26393 2026-09-05T19:41:58Z ddc:004 open_access

Tight Algorithm and Hardness for Submodular Linear Ordering Abboud, Evan Schwartz, Roy Submodular optimization approximation algorithms hardness of approximation linear ordering combinatorial optimization We consider the Minimum Linear Ordering Problem: given a ground set N of cardinality n and a non-negative set function f: 2^N → ℝ_{≥0}, the goal is to find an ordering π of N that minimizes the sum of the values of f over all prefixes of π. This problem has been studied for various classes of set functions, and the case of a submodular f is of special interest, as it captures classic problems including Minimum Linear Arrangement and Minimum Containing Interval Graph. In this work, we resolve the approximability of the Minimum Linear Ordering Problem for a general submodular f by establishing matching upper and lower bounds and present: (1) a polynomial-time algorithm achieving an O(√{n/ln n})-approximation; and (2) a matching information-theoretic hardness result, showing that no algorithm evaluating f a polynomial number of times can achieve an o(√{n/ln n})-approximation. Previously, the best known hardness of approximation was 2, and an O(√{n/ln n})-approximation was known only for the special case where f is both submodular and symmetric. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Evan Abboud and Roy Schwartz 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.4 urn:nbn:de:0030-drops-263932 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode