Pith. sign in

REVIEW 3 minor 41 references

The Minimum Linear Ordering Problem for submodular functions admits a tight O(sqrt(n/ln n)) approximation in the value oracle model.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-26 15:22 UTC pith:TOLGVN5Z

load-bearing objection This paper gives the first tight O(sqrt(n/ln n)) approximation and matching information-theoretic hardness for general submodular linear ordering.

arxiv 2606.20202 v1 pith:TOLGVN5Z submitted 2026-06-18 cs.DS

Tight Algorithm and Hardness for Submodular Linear Ordering

Evan Abboud , Roy Schwartz This is my paper
classification cs.DS
keywords submodular functionslinear orderingapproximation algorithmshardness of approximationvalue oracle modelminimum linear arrangementprefix sums
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper considers the problem of ordering a ground set of size n to minimize the sum of a non-negative submodular function f evaluated on all prefixes of the ordering. It supplies a polynomial-time algorithm that returns an ordering whose cost is at most O(sqrt(n/ln n)) times the optimum. It also proves that any algorithm allowed only polynomially many direct evaluations of f cannot achieve an asymptotically better ratio. This pair of results pins down the approximability of the problem exactly, improving on a prior constant-factor hardness and on an approximation known only for the symmetric special case.

Core claim

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(sqrt(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(sqrt(n/ln n))-approximation.

What carries the argument

The value-oracle access model for the submodular function f together with a new polynomial-time ordering procedure that produces the stated approximation ratio.

Load-bearing premise

Any algorithm is restricted to learning the submodular function only through polynomially many direct evaluations.

What would settle it

An algorithm that makes only polynomially many evaluations of f and returns an ordering whose cost is o(sqrt(n/ln n)) times the optimum on every instance would falsify the hardness claim.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • The approximability gap for general submodular linear ordering is closed in the value-oracle model.
  • The same O(sqrt(n/ln n)) guarantee applies to every special case previously studied, including Minimum Linear Arrangement.
  • No polynomial-query algorithm can improve the ratio by more than a constant factor.
  • The earlier 2-hardness result is strengthened to a tight super-constant bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If an algorithm were allowed arbitrary non-oracle access to f, the information-theoretic barrier would no longer apply.
  • The result suggests that submodular ordering problems may require query complexity that grows with n to beat the sqrt(n) barrier.
  • Similar tight bounds may hold for other ordering objectives that reduce to prefix-sum minimization under submodularity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper considers the Minimum Linear Ordering Problem for a non-negative submodular set function f on a ground set of size n. It claims to resolve the approximability gap by giving a polynomial-time O(√(n / ln n))-approximation algorithm and a matching information-theoretic hardness result: no algorithm making polynomially many queries to an oracle for f can achieve an o(√(n / ln n))-approximation. The result improves on a prior constant-factor hardness of 2 and extends an O(√(n / ln n)) guarantee that was previously known only for symmetric submodular functions.

Significance. If the stated bounds hold, the work closes a long-standing gap in submodular optimization by establishing asymptotically tight approximability for a problem that generalizes Minimum Linear Arrangement and Minimum Containing Interval Graph. The combination of a new polynomial-time algorithm with a matching query-complexity lower bound is a notable strength; the information-theoretic nature of the hardness makes the result robust within the standard value-oracle model.

minor comments (3)
  1. The abstract and introduction should explicitly state the precise query model (value oracle with polynomially many calls) in the hardness statement to avoid any ambiguity about the scope of the lower bound.
  2. Notation for the ordering π and the prefix sums should be introduced once and used consistently; a short table of notation would improve readability in the technical sections.
  3. The running-time analysis of the algorithm should include the exact number of oracle calls as a function of n, even if it is polynomial.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. The report correctly captures our main results on the tight O(√(n/ln n)) approximation and matching information-theoretic hardness for the Minimum Linear Ordering Problem under general non-negative submodular functions.

Circularity Check

0 steps flagged

No significant circularity; bounds are independently established

full rationale

The paper presents a new polynomial-time algorithm achieving the O(√(n/ln n)) approximation and a separate information-theoretic hardness proof showing that o(√(n/ln n)) is impossible under polynomially many oracle queries to f. These are matching but not circular: the algorithm is an explicit construction whose query cost matches the hardness model, while the lower bound is proven directly in the query model without reducing to the algorithm or to any self-citation chain. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the stated claims or abstract. The result is self-contained against the stated query-model benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard assumptions of theoretical computer science rather than new free parameters or invented entities.

axioms (1)
  • domain assumption Algorithms have access to the set function f only via direct evaluations, and the hardness holds in the polynomial-query information-theoretic model.
    Explicitly stated in the abstract as the model for the hardness result.

pith-pipeline@v0.9.1-grok · 5755 in / 1268 out tokens · 32328 ms · 2026-06-26T15:22:09.522601+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Tight Algorithm and Hardness for Submodular Linear Ordering." pith.science (2026). https://pith.science/paper/TOLGVN5Z

@misc{pith2026260620202,
  author       = {Pith},
  title        = {Pith review of: Tight Algorithm and Hardness for Submodular Linear Ordering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TOLGVN5Z}},
  note         = {Machine review of arXiv:2606.20202}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We consider the Minimum Linear Ordering Problem: given a ground set $N$ of cardinality $n$ and a non-negative set function $f\colon 2^N\rightarrow \mathbb{R}_{\geq 0}$, the goal is to find an ordering $\pi$ of $N$ that minimizes the sum of the values of $f$ over all prefixes of $\pi$. 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(\sqrt{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(\sqrt{n/\ln n})$-approximation. Previously, the best known hardness of approximation was $2$, and an $O(\sqrt{n/\ln n})$-approximation was known only for the special case where $f$ is both submodular and symmetric.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Expander flows, geometric embeddings and graph partitioning.Journal of the ACM (JACM), 56(2):1–37, 2009

    Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning.Journal of the ACM (JACM), 56(2):1–37, 2009

    2009

  2. [2]

    Submodular max-sat

    Yossi Azar, Iftah Gamzu, and Ran Roth. Submodular max-sat. InEuropean Symposium on Algorithms, pages 323–334. Springer, 2011

    2011

  3. [3]

    Improved approximations for min sum vertex cover and generalized min sum set cover

    Nikhil Bansal, Jatin Batra, Majid Farhadi, and Prasad Tetali. Improved approximations for min sum vertex cover and generalized min sum set cover. InProceedings of the 2021 ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 998–1005. SIAM, 2021

    2021

  4. [4]

    Concentration inequalities for sampling without replacement

    Rémi Bardenet and Odalric-Ambrym Maillard. Concentration inequalities for sampling with- out replacement.arXiv preprint arXiv:1309.4029, 2013. 16

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  5. [5]

    Improved approximation for min-sum vertex cover

    Uri Barenholz, Uriel Feige, David Peleg, et al. Improved approximation for min-sum vertex cover. Technical Report MCS06-07, Computer Science and Applied Mathematics, Weizmann Institute of Science, 2006

    2006

  6. [6]

    Bhatt and Frank Thomson Leighton

    Sandeep N. Bhatt and Frank Thomson Leighton. A framework for solving VLSI graph layout problems.J. Comput. Syst. Sci., 28(2):300–343, 1984

    1984

  7. [7]

    Moses Charikar, Mohammad Taghi Hajiaghayi, Howard Karloff, and Satish Rao.ℓ2 2 spreading metrics for vertex ordering problems.Algorithmica, 56(4):577–604, 2010

    2010

  8. [8]

    The minsumcut problem

    Josep Díaz, AM Gibbons, MS Paterson, and Jacobo Toran. The minsumcut problem. In Workshop on Algorithms and Data Structures, pages 65–79. Springer, 1991

    1991

  9. [9]

    From query complexity to computational complexity

    Shahar Dobzinski and Jan Vondrák. From query complexity to computational complexity. InProceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1107–1116, 2012

    2012

  10. [10]

    Local distribution and the symmetry gap: Approx- imability of multiway partitioning problems

    Alina Ene, Jan Vondrák, and Yi Wu. Local distribution and the symmetry gap: Approx- imability of multiway partitioning problems. InProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 306–325. SIAM, 2013

    2013

  11. [11]

    Divide-and-conquer approxi- mation algorithms via spreading metrics.Journal of the ACM (JACM), 47(4):585–616, 2000

    Guy Even, Joseph Seffi Naor, Satish Rao, and Baruch Schieber. Divide-and-conquer approxi- mation algorithms via spreading metrics.Journal of the ACM (JACM), 47(4):585–616, 2000

    2000

  12. [12]

    Hardness and approximation of submodular minimum linear ordering problems.Mathematical Program- ming, 208(1):277–318, 2024

    Majid Farhadi, Swati Gupta, Shengding Sun, Prasad Tetali, and Michael C Wigal. Hardness and approximation of submodular minimum linear ordering problems.Mathematical Program- ming, 208(1):277–318, 2024

    2024

  13. [13]

    Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algo- rithms for minimum weight vertex separators.SIAM Journal on Computing, 38(2):629–657, 2008

    2008

  14. [14]

    An improved approximation ratio for the minimum linear arrangement problem.Information Processing Letters, 101(1):26–29, 2007

    Uriel Feige and James R Lee. An improved approximation ratio for the minimum linear arrangement problem.Information Processing Letters, 101(1):26–29, 2007

    2007

  15. [15]

    Approximating min sum set cover.Algorithmica, 40(4):219–234, 2004

    Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover.Algorithmica, 40(4):219–234, 2004

    2004

  16. [16]

    Maximizing non-monotone submodular functions.SIAM Journal on Computing, 40(4):1133–1153, 2011

    Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions.SIAM Journal on Computing, 40(4):1133–1153, 2011

    2011

  17. [17]

    Separating coverage and submodular: Maximization subject to a cardinality constraint

    Yuval Filmus, Roy Schwartz, and Alexander V Smal. Separating coverage and submodular: Maximization subject to a cardinality constraint. InInternational Conference on Integer Programming and Combinatorial Optimization, pages 242–255. Springer, 2025

    2025

  18. [18]

    Submodular maximization by simulated annealing

    Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. InProceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1098–1116. SIAM, 2011

    2011

  19. [19]

    Approximability of com- binatorial problems with multi-agent submodular cost functions

    Gagan Goel, Chinmay Karande, Pushkar Tripathi, and Lei Wang. Approximability of com- binatorial problems with multi-agent submodular cost functions. In2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 755–764. IEEE Computer Society, 2009. 17

    2009

  20. [20]

    Approximat- ing submodular functions everywhere

    Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. Approximat- ing submodular functions everywhere. InProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 535–544. SIAM, 2009

    2009

  21. [21]

    The ellipsoid method and its consequences in combinatorial optimization.Combinatorica, 1:169–197, 1981

    Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization.Combinatorica, 1:169–197, 1981

    1981

  22. [22]

    An approximation algorithm for the minimum latency set cover problem

    Refael Hassin and Asaf Levin. An approximation algorithm for the minimum latency set cover problem. InEuropean Symposium on Algorithms, pages 726–733. Springer, 2005

    2005

  23. [23]

    Probability inequalities for sums of bounded random variables.Journal of the American statistical association, 58(301):13–30, 1963

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American statistical association, 58(301):13–30, 1963

    1963

  24. [24]

    A combinatorial strongly polynomial algo- rithm for minimizing submodular functions.J

    Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial strongly polynomial algo- rithm for minimizing submodular functions.J. ACM, 48(4):761–777, July 2001

    2001

  25. [25]

    Submodular function minimization under covering con- straints

    Satoru Iwata and Kiyohito Nagano. Submodular function minimization under covering con- straints. In2009 50th annual IEEE symposium on foundations of computer science, pages 671–680. IEEE, 2009

    2009

  26. [26]

    Approximating minimum linear order- ing problems

    Satoru Iwata, Prasad Tetali, and Pushkar Tripathi. Approximating minimum linear order- ing problems. InInternational Workshop on Approximation Algorithms for Combinatorial Optimization, pages 206–217. Springer, 2012

    2012

  27. [27]

    A simple algorithm for submodular minimum linear order- ing

    Dor Katzelnick and Roy Schwartz. A simple algorithm for submodular minimum linear order- ing. InSymposium on Simplicity in Algorithms (SOSA), pages 28–35. SIAM, 2023

    2023

  28. [28]

    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM (JACM), 46(6):787–832, 1999

    Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM (JACM), 46(6):787–832, 1999

    1999

  29. [29]

    Profile minimization problem for matrices and graphs.Acta Mathematicae Applicatae Sinica, 10:107–112, 1994

    Yixun Lin and Jinjiang Yuan. Profile minimization problem for matrices and graphs.Acta Mathematicae Applicatae Sinica, 10:107–112, 1994

    1994

  30. [30]

    Submodular functions and convexity

    László Lovász. Submodular functions and convexity. InMathematical Programming The State of the Art: Bonn 1982, pages 235–257. Springer, 1983

    1982

  31. [31]

    Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

    Vahab Mirrokni, Michael Schapira, and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. InProceedings of the 9th ACM conference on Electronic commerce, pages 70–77, 2008

    2008

  32. [32]

    G. L. Nemhauser and M. L. Fisher. Best algorithms for approximating the maximum of a submodular set function.Mathematics of Operations Research, 3(3):177–188, 1978

    1978

  33. [33]

    Ramalingam and C.Pandu Rangan

    G. Ramalingam and C.Pandu Rangan. A unified approach to domination problems on interval graphs.Information Processing Letters, 27(5):271–274, 1988

    1988

  34. [34]

    New approximation techniques for some linear ordering problems.SIAM Journal on Computing, 34(2):388–404, 2005

    Satish Rao and Andréa W Richa. New approximation techniques for some linear ordering problems.SIAM Journal on Computing, 34(2):388–404, 2005

    2005

  35. [35]

    Ordering problems approximated: single- processor scheduling and interval graph completion

    Ramamurthy Ravi, Ajit Agrawal, and Philip Klein. Ordering problems approximated: single- processor scheduling and interval graph completion. InInternational Colloquium on Automata, Languages, and Programming, pages 751–762. Springer, 1991. 18

    1991

  36. [36]

    Multivariate submodular optimization

    Richard Santiago and F Bruce Shepherd. Multivariate submodular optimization. InInterna- tional Conference on Machine Learning, pages 5599–5609. PMLR, 2019

    2019

  37. [37]

    A combinatorial algorithm minimizing submodular functions in strongly polynomial time.Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000

    Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time.Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000

    2000

  38. [38]

    Paul D. Seymour. Packing directed circuits fractionally.Combinatorica, 15(2):281–288, 1995

    1995

  39. [39]

    Some Results on Approximability of Minimum Sum Vertex Cover

    Aleksa Stanković. Some Results on Approximability of Minimum Sum Vertex Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), volume 245, pages 50:1–50:16, 2022

    2022

  40. [40]

    Submodular approximation: Sampling-based algorithms and lower bounds.SIAM Journal on Computing, 40(6):1715–1737, 2011

    Zoya Svitkina and Lisa Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds.SIAM Journal on Computing, 40(6):1715–1737, 2011

    2011

  41. [41]

    Symmetry and approximability of submodular maximization problems.SIAM Journal on Computing, 42(1):265–304, 2013

    Jan Vondrák. Symmetry and approximability of submodular maximization problems.SIAM Journal on Computing, 42(1):265–304, 2013. A Missing Proofs: Algorithm 1 Lemma 12.Letβ∈(0,1)be a fixed constant and letD≤ln(n/2)/ln(1/β). Then, D∑ i=0 √ βin ln(βin) =O (√ n lnn ) . Proof.From the assumption onD, we haveβDn≥2, and since0<β <1, this impliesβin≥2for all0≤i≤D, ...

    2013