DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.4

Tight Algorithm and Hardness for Submodular Linear Ordering

Authors: Evan Abboud and Roy Schwartz

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Evan Abboud and Roy Schwartz. Tight Algorithm and Hardness for Submodular Linear Ordering. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ICALP.2026.4,
  author =	{Abboud, Evan and Schwartz, Roy},
  title =	{{Tight Algorithm and Hardness for Submodular Linear Ordering}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.4},
  URN =		{urn:nbn:de:0030-drops-263932},
  doi =		{10.4230/LIPIcs.ICALP.2026.4},
  annote =	{Keywords: Submodular optimization, approximation algorithms, hardness of approximation, linear ordering, combinatorial optimization}
}

Search Results

Documents authored by Abboud, Evan

Tight Algorithm and Hardness for Submodular Linear Ordering

Abstract

Cite as

Thanks for your feedback!

Could not send message