Tight Algorithm and Hardness for Submodular Linear Ordering

Abboud, Evan; Schwartz, Roy

doi:10.4230/LIPIcs.ICALP.2026.4

Tight Algorithm and Hardness for Submodular Linear Ordering

Evan Abboud

Technion – Israel Institute of Technology, Haifa, Israel Roy Schwartz

Technion – Israel Institute of Technology, Haifa, Israel

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.

Keywords and phrases:

Submodular optimization, approximation algorithms, hardness of approximation, linear ordering, combinatorial optimization

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis ; Theory of computation

\rightarrow

Submodular optimization and polymatroids

Acknowledgements:

The authors would like to thank Yuval Filmus for stimulating discussions.

Funding:

Evan Abboud and Roy Schwartz received funding from the European Union’s Horizon 2020 research and innovation program under grant agreement no. 852870-ERC-SUBMODULAR and ISF grant 3264/25.

DOI:

10.4230/LIPIcs.ICALP.2026.4

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

We consider the Minimum Linear Ordering Problem (MLOP). In this problem, we are given a ground set $N$ of cardinality $n$ and a non-negative set function $f\colon 2^{N}\to\mathbb{R}_{\geq 0}$ . The goal is to find an ordering of the elements of $N$ , i.e., a permutation $\pi\colon N\to\{1,\ldots,n\}$ , that minimizes the sum of the values of $f$ over all prefixes of $\pi$ . Formally, the goal is to minimize:

\displaystyle\sum_{i=1}^{n-1}f(N_{\pi,i}),

(1.1)

where $N_{\pi,i}$ denotes the first $i$ elements of $N$ with respect to $\pi$ , i.e., $N_{\pi,i}\triangleq\{u\in N\colon\pi(u)\leq i\}$ . For simplicity of presentation, we denote by $\operatorname{val}(\pi)\triangleq\sum_{i=1}^{n-1}f(N_{\pi,i})$ the objective value of an ordering $\pi$ .

The problem was introduced in its full generality by Iwata, Tetali and Tripathi [24]¹¹1The objective in [24] is defined by summing over $i=0,\ldots,n$ , which differs from the above definition by the ordering-independent term $f(\varnothing)+f(N)$ , where $f(\varnothing)$ corresponds to $i=0$ and $f(N)$ corresponds to $i=n$ . Since $f$ is non-negative, removing $i=0$ and $i=n$ from the sum can only improve multiplicative approximation guarantees. , and has been studied for various types of set functions and special cases. Two notable types of set functions are submodular and supermodular functions. A set function $f\colon 2^{N}\to\mathbb{R}$ is submodular if:

\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B),\nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \forall A,B\subseteq N,

and $f$ is supermodular if $-f$ is submodular.

For a supermodular $f$ , MLOP captures the classic Minimum Sum Set Cover problem. In this problem, the ground set $N$ consists of $n$ sets that cover $m$ elements. Given an ordering $\pi$ of $N$ , every element is associated with a cover-time: the position of the first set in $\pi$ that covers the element. The goal is to find an ordering $\pi$ that minimizes the sum of cover-times over all $m$ elements. An interesting special case of Minimum Sum Set Cover is Minimum Sum Vertex Cover, where each element appears in two sets.

The study of both Minimum Sum Set Cover and Minimum Sum Vertex Cover was initiated by Feige, Lovász and Tetali [15], and has admitted improved upper and lower bounds since its introduction, e.g., [5, 3, 24, 36] (the reader is referred to Section 1.3 for a brief overview of related work). For a general non-negative supermodular $f$ , the approximability of MLOP is resolved. A $4$ -approximation is given by [24], and a matching hardness is given by [15]: for every $\varepsilon>0$ achieving an approximation of $(4-\varepsilon)$ for Minimum Sum Set Cover is NP-hard.

For a submodular $f$ , MLOP captures several fundamental graph ordering problems. Two prominent examples include Minimum Linear Arrangement and Minimum Containing Interval Graph, whose study dates back as early as the work of Leighton and Rao [26] (Minimum Containing Interval Graph is also known as Minimum SumCut, see, e.g., Díaz, Gibbons, Paterson and Toran [8], and as Minimum Profile, see, e.g., Lin and Yuan [27]). In both problems, we are given an undirected graph $G=(V,E)$ where $(1)$ in the former problem, the goal is to find an ordering $\pi$ of $V$ that minimizes the total length of edges in the ordering: $\sum_{(u,v)\in E}|\pi(u)-\pi(v)|$ ; and $(2)$ in the latter problem, the goal is to find an interval graph $G^{\prime}=(V,E^{\prime})$ on the same nodes as $G$ that contains $G$ as a subgraph, i.e., $E\subseteq E^{\prime}$ , and minimizes $|E^{\prime}|$ .

Clearly, MLOP captures Minimum Linear Arrangement as a special case with a symmetric submodular $f$ that is the cut function of $G$ , i.e., $f(S)$ equals the number of edges of $G$ that cross the cut $S$ . To see why MLOP captures Minimum Containing Interval Graph, the classic characterization of Ramalingam and Pandu Rangan [31] is utilized: a graph $G=(V,E)$ is an interval graph if and only if there exists an ordering $\pi$ of $V$ such that for every edge $(u,v)\in E$ , if $\pi(u)<\pi(v)$ , then for every node $w$ satisfying $\pi(u)<\pi(w)<\pi(v)$ there exists an edge connecting $w$ and $v$ . Thus, choosing a submodular, but not symmetric, $f$ that is the node cut function of $G$ , i.e., $f(S)$ equals the number of nodes outside of $S$ that have neighbors in $S$ , establishes that Minimum Containing Interval Graph is captured by MLOP with a general submodular and non-symmetric $f$ . The study of both Minimum Linear Arrangement and Minimum Containing Interval Graph has attracted much attention in recent decades, e.g., [1, 6, 7, 11, 13, 14, 26, 32, 33, 35] (the reader is referred to Section 1.3 for a brief overview of related work).

In contrast to MLOP with a supermodular $f$ , which is resolved, much less is known for MLOP with a submodular $f$ . Results are known for only two special cases of a submodular $f$ . First, consider the special case that $f$ is submodular and monotone, i.e., $f(A)\leq f(B)$ , $\forall A\subseteq B\subseteq N$ (MLOP with a monotone submodular $f$ captures additional applications, e.g., the Minimum Latency Set Cover problem; see, e.g., Hassin and Levin [21]). For this special case, [24] presented an approximation of $2(1-1/(n+1))$ . This bound was further improved for specific monotone submodular functions $f$ by Farhadi, Gupta, Sun, Tetali and Wigal [12]. Second, consider the special case that $f$ is submodular and symmetric, i.e., $f(A)=f(N\setminus A)$ , $\forall A\subseteq N$ . For this special case, it is known that any ordering $\pi$ provides an approximation of $O(n)$ [12] and an improved approximation of $O(\sqrt{n/\ln{n}})$ is given by Katzelnick and Schwartz [25]. For this special case, [24] show that for every $\varepsilon>0$ any algorithm that evaluates $f$ a polynomial number of times cannot achieve an approximation of $(2-\varepsilon)$ .

Summarizing, while the approximability of MLOP with a supermodular $f$ is resolved, much less is known when $f$ is submodular. Specifically, for a general (not necessarily monotone or symmetric) submodular $f$ , the best known hardness bound for MLOP is $2$ , and no approximation algorithm is known to the best of our knowledge. The goal of this work is to close this gap.

Value-Oracle Model

As is typical in submodular optimization problems, we assume that the algorithm is not given $f$ explicitly, but can access $f$ using a value-oracle as follows: for every $S\subseteq N$ , the algorithm can query the oracle and obtain $f(S)$ . Hence, the running time of the algorithm is measured by the number of value-oracle queries it performs (as well as the number of arithmetic operations).

1.1 Our Result

In this work, we resolve the approximability of MLOP with a general non-negative submodular $f$ .

First, we present an algorithm that achieves an approximation of $O(\sqrt{n/\ln{n}})$ for MLOP, as is summarized by the following theorem.

Theorem 1.

There exists a polynomial-time algorithm that, given a non-negative submodular set function $f$ over a ground set $N$ of size $n$ , outputs an ordering $\pi$ of $N$ such that:

\operatorname{val}(\pi)\leq O\!\left(\sqrt{n/\ln{n}}\right)\cdot\operatorname{% OPT}.

Here, $\operatorname{OPT}$ denotes the value of an optimal solution to the given instance of the Minimum Linear Ordering Problem.

Previously, an approximation of $O(\sqrt{n/\ln{n}})$ , given by Katzelnick and Schwartz [25], was known only in the special case where $f$ is not only submodular but also symmetric. To the best of our knowledge, no algorithm for MLOP with a general non-negative submodular $f$ was previously known. It should be noted that our algorithm differs from the algorithm of [25], as the latter algorithm and its analysis are crucially based on the symmetry of $f$ . Thus, a new approach is required (see Section 1.2 for an overview of our techniques).

Second, we present a hardness result for MLOP that matches the guarantee of Theorem 1, as is summarized by the following theorem.

Theorem 2.

No (possibly randomized) algorithm that makes a polynomial number in $n$ of value-oracle queries can achieve an $o(\sqrt{n/\ln n})$ -approximation for the Minimum Linear Ordering Problem with a non-negative submodular objective $f$ over a ground set $N$ of size $n$ .

There are two things to note regarding Theorem 2. First, the hardness result in Theorem 2 improves the previously best known hardness of $2$ , which was given by Iwata, Tetali and Tripathi [24], and asymptotically matches the $O(\sqrt{n/\ln{n}})$ -approximation guarantee of Theorem 1. Thus, the approximability of MLOP with a submodular $f$ is resolved. Second, it should be noted that the hardness result of Theorem 2, as is common for submodular optimization problems in the value-oracle model, is information-theoretic and does not rely on any computational complexity assumptions.

1.2 Our Techniques

Algorithmic Approach

A classic framework of recursive balanced cutting, which dates back to Bhatt and Leighton [6], can be successfully applied to many graph ordering problems. In a nutshell, given a subset of vertices $A$ , the algorithm: $(1)$ computes a suitable balanced cut $S\subseteq A$ in the subgraph $G[A]$ induced by $A$ ; $(2)$ places the vertices of $S$ before the vertices of $A\setminus S$ ; and $(3)$ recurses on $G[S]$ and $G[A\setminus S]$ , the subgraphs induced by $S$ and $A\setminus S$ , respectively, to determine the ordering within each part. For example, a suitable balanced cut problem in step $(1)$ above is the classic Minimum $b$ -Balanced Cut problem for Minimum Linear Arrangement and the classic Node $\rho$ -Separator problem for Minimum Containing Interval Graph.

Roughly speaking, if one has an $\alpha$ -approximation for the relevant balanced cut problem, it is known that the above framework provides an approximation of $O(\alpha\ln{n})$ for many ordering problems, including both Minimum Linear Arrangement and Minimum Containing Interval Graph. Intuitively, two essential structural observations enable one to prove this approximation. To simplify the presentation of these observations and keep the discussion as informal as possible, in what follows we focus on Minimum Linear Arrangement (a similar discussion involving nodes, as opposed to edges, also applies to Minimum Containing Interval Graph). First, each recursive call operates on $G[A]$ , i.e., an induced subgraph whose nodes are exactly $A$ and whose edges consist only of edges with both endpoints in $A$ . Consequently, once a cut is made, edges crossing between the two sides $S$ and $A\setminus S$ are permanently removed. Second, the objective function changes across recursive calls, as it becomes the cut function of the relevant induced subgraph. Together, these two observations ensure that each edge is charged only once, resulting in the claimed approximation.

Unfortunately, when considering MLOP, these observations fail and the framework breaks down. The main reason is that there is no clear notion of an induced subproblem, since the input consists only of $N$ and the set function $f$ . Therefore, there is no obvious underlying structure that can be deleted as the recursion proceeds. Moreover, it can be easily shown that trivially applying the recursive balanced cutting framework by recursively computing balanced cuts on each subset $A$ with respect to the original $f$ fails.

Katzelnick and Schwartz [25] address this difficulty for the special case where $f$ is not only submodular but also symmetric. Specifically, when recursing on $A$ , [25] find a balanced cut $S\subseteq A$ of $A$ while using a different objective function. Intuitively, $f$ is modified in a manner that depends on $A$ , allowing one to mimic the induced subgraph behavior and the proof of the recursive balanced cutting framework for Minimum Linear Arrangement. However, this solution relies crucially on the symmetry of $f$ , and without it the algorithm of [25] is not even properly defined. Thus, a different approach is required when considering MLOP with a general, and not necessarily symmetric, submodular $f$ .

Our approach is remarkably simple: when recursing on $A$ , we find a global cut $S\subseteq N$ using the original set function $f$ , where the only requirement is that $S$ is balanced with respect to $A$ , i.e., $b\cdot\lvert A\rvert\leq\lvert S\cap A\rvert\leq(1-b)\cdot\lvert A\rvert$ for some constant $0<b<\nicefrac{{1}}{{2}}$ . Then, our algorithm places $S\cap A$ before $A\setminus(S\cap A)$ and recurses on both. Hence, instead of restricting the cut $S$ to be a subset of $A$ and changing the function $f$ , as is done when applying the recursive balanced cutting framework to Minimum Linear Arrangement and in [25] for MLOP with a symmetric submodular $f$ , we: $(1)$ compute the cut $S$ over the entire ground set $N$ ; and $(2)$ use the original $f$ throughout the recursion regardless of the current set $A$ .

At first glance, this approach appears to be inherently wasteful. To exemplify this intuition, focus on Minimum Linear Arrangement. For this problem, our approach reduces to the following when recursing on $A\subseteq V$ : we compute an $\alpha$ -approximate global cut $S\subseteq V$ that is balanced with respect to $A$ and minimizes the total number of edges crossing $S$ in the entire graph $G$ . Therefore, the cost of $S$ is determined also by edges outside of $G[A]$ , e.g., edges with both endpoints outside of $A$ that cross $S$ . Thus, the induced subgraph $G[A]$ is ignored when determining the cost of $S\subseteq V$ . Nonetheless, a surprising consequence of our work is that the above algorithm, which seems wasteful, also provides an approximation of $O(\alpha\ln{n})$ for Minimum Linear Arrangement.

To analyze our algorithm, we first observe that there is a one-to-one correspondence between (non-base) recursive calls and prefixes in the final ordering of the algorithm. We then prove that each prefix admits a recursive formula that consists of only union and intersection operations over the approximate balanced global cuts computed along the chain of recursive calls starting with the initial call on $N$ and ending with the recursive call corresponding to the prefix. The crucial observation is that each such balanced global cut appears exactly once in this formula, i.e., the formula is read-once. This property allows us to exploit the submodularity and non-negativity of $f$ to upper bound the value of the final ordering by a sum over all (non-base) recursive calls, where each (non-base) recursive call on $A$ contributes to this sum a value of $\lvert A\rvert\cdot f(S)$ (here $S\subseteq N$ is the $\alpha$ -approximate balanced global cut computed by the algorithm in the recursive call on $A$ ). This suffices to prove the desired upper bound on the value of the final ordering of the algorithm.

Hardness Approach

Our hardness is proved using an indistinguishability argument in the value-oracle model, a classic approach in submodular optimization, see, e.g., [30, 37, 16]. In this approach, one typically constructs two submodular functions: a deterministic function $f_{1}$ and a randomized function $f_{2}$ . The functions are required to be indistinguishable to any algorithm making a polynomial number of value-oracle queries, yet the values of their optimal solutions differ substantially. Thus, any algorithm making a polynomial number of value-oracle queries achieving an approximation better than the ratio of the optimal solutions would therefore be able to distinguish between $f_{1}$ and $f_{2}$ , contradicting their indistinguishability. Hence, the optima ratio translates into information-theoretic hardness of the same value.

Existing hardness constructions following this framework, including hardness constructions based on the symmetry gap machinery of Vondrák [38], typically hide a random set. Such constructions are well suited to various minimization and maximization submodular optimization problems whose solution is characterized by a single set. Unfortunately, such an approach is not sufficient for MLOP, whose solution consists of an ordering of the entire ground set $N$ . Consequently, these techniques do not yield a strong hardness result for MLOP (the current best known hardness for MLOP with a submodular $f$ equals only $2$ [24] and it is obtained by hiding a single random set).

Our construction differs in that the randomized function $f_{2}$ hides a uniform random ordering rather than just a set. Consequently, this results in incorporating all suffixes of the random ordering into the definition of $f_{2}$ . While this is essential for obtaining the desired gap for MLOP, it also introduces new challenges. The main challenge is that despite the many suffixes incorporated into the definition of $f_{2}$ , it must remain non-negative, submodular, and indistinguishable from $f_{1}$ . To guarantee that all of the above are achieved simultaneously for all possible random orderings, we leverage an observation of Lovász [28] that provides a sufficient condition when the minimum of two submodular functions is also submodular.

1.3 Related Work

Minimum Sum Set Cover was first considered by Feige, Lovász and Tetali [15], who presented an approximation of $4$ for it and showed that this approximation is tight by proving that, for every $\varepsilon>0$ , achieving an approximation of $(4-\varepsilon)$ is NP-hard. Minimum Sum Vertex Cover was also introduced in [15], who presented an approximation of $2$ , and this approximation was subsequently improved to $\approx 1.999946$ by Barenholz, Feige and Peleg [5] and to $\nicefrac{{16}}{{9}}$ by Bansal, Batra, Farhadi and Tetali [3], which is the current best known approximation. Focusing on lower bounds for Minimum Sum Vertex Cover, it was proved in [15] that there exists a constant $\rho>1$ for which it is NP-hard to obtain an approximation better than $\rho$ , and Stanković [36] proved that an approximation better than $1.014$ is not possible assuming the Unique Games Conjecture.

Both Minimum Linear Arrangement and Minimum Containing Interval Graph admit a rich history, and as previously mentioned, the recursive balanced cutting framework provides an approximation of $O(\alpha\ln{n})$ for both problems (where $\alpha$ is the approximation achieved for the relevant balanced cut problem). Specifically, for Minimum Linear Arrangement, Leighton and Rao [26] present an approximation algorithm with $\alpha=O(\ln{n})$ which was subsequently improved by Arora, Rao and Vazirani [1] to $O(\sqrt{\ln{n}})$ , yielding overall approximations of $O(\ln^{2}{n})$ and $O(\ln^{\nicefrac{{3}}{{2}}}{n})$ , respectively. Similarly, for Minimum Containing Interval Graph, Ravi, Agrawal and Klein [33] and Feige, Hajiaghayi and Lee [13] provide overall approximations of $O(\ln^{2}{n})$ and $O(\ln^{\nicefrac{{3}}{{2}}}{n})$ , respectively.

Going beyond recursive balanced cutting, both problems admit improved results: Even, Naor, Rao and Schieber [11] provide an overall approximation of $O(\ln{n}\ln{\ln{n}})$ using the cutting scheme of Seymour [35]; Rao and Richa [32] improve the approximation factor to $O(\ln{n})$ ; and finally, by building on the work of [1], both Charikar, Hajiaghayi, Karloff and Rao [7] and Feige and Lee [14] improve the approximation factor to $O(\sqrt{\ln{n}}\ln{\ln{n}})$ .

A substantial line of work has established hardness results for submodular optimization problems in the value-oracle model using indistinguishability-based constructions. This approach dates back to Nemhauser and Fisher [30] from the late $70$ ’s, and subsequent works have applied this approach to a wide range of submodular optimization problems, e.g., [16, 20, 37, 23, 19, 34, 29].

Indistinguishability-based constructions were subsequently captured by the symmetry gap machinery, introduced by Vondrák [38] to prove information-theoretic hardness bounds for submodular maximization problems. Since its introduction, the symmetry gap machinery has been used to obtain multiple value-oracle hardness results for a variety of problems, see, e.g., [18, 2, 17]. Subsequently, Ene, Vondrák, and Wu [10] showed that the symmetry gap machinery can also be used to derive value-oracle hardness results for submodular minimization problems. Moreover, Dobzinski and Vondrák [9] showed how symmetry gap based value-oracle hardness results can be translated into computational complexity inapproximability results, assuming $\text{NP}\neq\text{RP}$ , when $f$ is given explicitly.

Paper Organization

Section 2 contains several required preliminary results. Section 3 focuses on our algorithm, whereas Section 4 contains the hardness result.

2 Preliminaries

Throughout the paper $\operatorname{OPT}$ denotes the value of an optimal solution for MLOP.

Submodular $𝒃$ -Balanced Cut

Our algorithm requires an approximation algorithm to a weighted variant of the Minimum Submodular $b$ -Balanced Cut problem. In the Minimum Submodular $b$ -Balanced Cut problem, we are given a ground set $V$ of size $n$ that is equipped with non-negative weights $w\colon V\rightarrow\mathbb{R}_{\geq 0}$ , a non-negative submodular function $f\colon 2^{V}\rightarrow\mathbb{R}_{\geq 0}$ , and a balancing parameter $b<\nicefrac{{1}}{{2}}$ . A subset $A\subseteq V$ is a $b$ -balanced cut if $b\cdot w(V)\leq w(A)\leq(1-b)\cdot w(V)$ , where $w(S)\triangleq\sum_{u\in S}w(u)$ for every $S\subseteq V$ . The goal is to find a $b$ -balanced cut $A\subseteq V$ minimizing $f(A)$ :

\displaystyle\min\{f(A)\colon A\subseteq V,\;b\cdot w(V)\leq w(A)\leq(1-b)% \cdot w(V)\}.

The following theorem was given by Svitkina and Fleischer [37] and it provides a bicriteria approximation for Minimum Submodular $b$ -Balanced Cut.

Theorem 3 (Svitkina and Fleischer [37]).

There exists a polynomial time algorithm that given a ground set $V$ of size $n$ equipped with non-negative weights $w\colon V\to\mathbb{R}_{\geq 0}$ , a non-negative submodular function $f\colon 2^{V}\rightarrow\mathbb{R}_{\geq 0}$ , a balancing parameter $0<b\leq\nicefrac{{1}}{{2}}$ , and a bicriteria parameter $0<b^{\prime}<b$ , finds a $\nicefrac{{b^{\prime}}}{{2}}$ -balanced cut $S\subseteq V$ satisfying:

\displaystyle f(S)\leq O\left(\frac{\sqrt{k/\ln{k}}}{b-b^{\prime}}\right)\cdot% \min\{f(A)\colon A\subseteq V,\;b\cdot w(V)\leq w(A)\leq(1-b)\cdot w(V)\},

where $k=\lvert\{u\in V\colon w(u)>0\}\rvert$ is the size of the support of $w$ .

There are two things to note regarding Theorem 3: $(1)$ the approximation guarantee proved in [37] is only $O(\sqrt{n/\ln{n}}/(b-b^{\prime}))$ and not $O(\sqrt{k/\ln{k}}/(b-b^{\prime}))$ , however essentially the same algorithm and proof as in [37] provide the improved guarantee of Theorem 3; and $(2)$ the algorithm of [37] is randomized and fails with a probability that is arbitrarily small, e.g., exponentially small in $n$ , however to simplify presentation throughout the paper we explicitly omit any discussion on success probability and condition on a successful execution of the algorithm of Theorem 3. A formal discussion regarding both points above appears in the full version of the paper.

Submodularity Preserving Operations

Our tight information-theoretic hardness result requires the following lemma given by Lovász [28].

Lemma 4 (Lovász [28]).

Let $f$ and $g$ be two submodular set functions over the same ground set such that $f-g$ is either monotone non-decreasing or monotone non-increasing. Then, the set function $\min\{f,g\}$ is also submodular.

Indistinguishability

We say that an algorithm distinguishes two functions $f_{1}$ and $f_{2}$ if its output differs when given value oracle access to $f_{1}$ versus value oracle access to $f_{2}$ . The following lemma, due to Svitkina and Fleischer [37], is used to establish an approximation lower bound in the value-oracle model; it requires two conditions: the first is sufficient to guarantee oracle indistinguishability between the functions, and the second requires a multiplicative gap between their optimal objective values.

Lemma 5 (Svitkina and Fleischer [37]).

Let $\mathcal{P}$ be a minimization problem defined on set functions over a ground set $N$ of size $n$ . If there exist a set function $f_{1}$ on $N$ and a distribution $\mathcal{D}$ over set functions on $N$ such that $(1)$ for every set $S\subseteq N$ , $\Pr_{f_{2}\sim\mathcal{D}}\!\left[f_{1}(S)\neq f_{2}(S)\right]\leq n^{-\omega(% 1)}$ ; and $(2)$ for every $f_{2}$ drawn from $\mathcal{D}$ , $\operatorname{OPT}_{1}\geq\gamma\cdot\operatorname{OPT}_{2}$ for some $\gamma\geq 1$ , where $\operatorname{OPT}_{1}$ and $\operatorname{OPT}_{2}$ denote the optimal values of $\mathcal{P}$ on inputs $f_{1}$ and $f_{2}$ , respectively, then no (possibly randomized) algorithm making a polynomial number of value-oracle queries can approximate $\mathcal{P}$ within a factor of $o(\gamma)$ .

3 $O\left(\sqrt{n/\ln{n}}\right)$ -Approximation Algorithm

As mentioned in Section 1.2, at a high level, our algorithm is inspired by the classic recursive balanced cutting framework, which has been extensively used in the literature for various ordering problems, see, e.g., Leighton and Rao [26] and the references therein. However, two key differences distinguish our approach from the recursive balanced cutting framework: $(1)$ the balanced cut $S$ is computed over the entire ground set $N$ regardless of the current $A$ , where $S$ only needs to be balanced with respect to $A$ ; and $(2)$ the original $f$ is used regardless of $A$ .

Specifically, given $A\subseteq N$ , let $\mathbf{1}_{A}$ denote the weight function that assigns a weight of $1$ to elements of $A$ and a weight of $0$ to all other elements, and the algorithm splits $A$ as follows: $(1)$ it computes an approximate Minimum Submodular $b$ -Balanced Cut $S\subseteq N$ of the entire ground set $N$ with element weights $w=\mathbf{1}_{A}$ and the given $f$ (as well as constants $b$ and $b^{\prime}$ as in Theorem 3); $(2)$ it places the elements of $S\cap A$ before the elements of $A\setminus(S\cap A)$ , i.e., the elements of $S\cap A$ are placed to the left of the elements of $A\setminus(S\cap A)$ ; and $(3)$ it recurses on $S\cap A$ and $A\setminus(S\cap A)$ . The initial recursive invocation of the algorithm is performed with $A=N$ .

To simplify presentation, for two orderings $\pi_{1}$ of $A\subseteq N$ and $\pi_{2}$ of $B\subseteq N$ , where $A\cap B=\varnothing$ , denote by $\pi_{1}\circ\pi_{2}$ the ordering of $A\cup B$ obtained by concatenating $\pi_{2}$ after $\pi_{1}$ , i.e., all elements of $A$ are placed before (to the left of) all elements of $B$ and the order between elements of $A$ is determined by $\pi_{1}$ and the order between elements of $B$ is determined by $\pi_{2}$ .

Algorithm 1 Recursive Balanced Global Cutting.

Analysis Notations

We introduce the following notations to simplify the analysis. First, denote by $\mathcal{A}$ the collection of sets $A\subseteq N$ for which Algorithm 1 invokes the approximation algorithm of Theorem 3 for Minimum Submodular $b$ -Balanced Cut, i.e., the non-base recursive calls. Second, for any $A\in\mathcal{A}$ , denote by $h(A)\subseteq N$ the set of elements Algorithm 1 places strictly before $A$ in the final ordering, i.e., elements placed to the left of $A$ in the final ordering. Third and last, for every $A\in\mathcal{A}$ , denote by $\operatorname{Alg}(A)\subseteq N$ the set of elements returned by the Minimum Submodular $b$ -Balanced Cut algorithm of Theorem 3 when executed on $(N,f,w)$ with $w=\mathbf{1}_{A}$ , $b=\nicefrac{{1}}{{4}}$ , and $b^{\prime}=\nicefrac{{1}}{{8}}$ (line 5 of Algorithm 1).

Following the above notations, one can view the execution of Algorithm 1 as inducing a decomposition tree whose internal (non-leaf) nodes are $\mathcal{A}$ , which has $n$ leaves each corresponding to a different element of $N$ , and whose root is $N$ . Given an internal node $A\in\mathcal{A}$ , $A$ has two children: the left child is $S\cap A$ and the right child is $A\setminus(S\cap A)$ (recall that $S\subseteq N$ is the approximate Minimum Submodular $b$ -Balanced Cut found by Algorithm 1 in line 5). Moreover, for every $i\geq 0$ , denote by $\mathcal{A}_{i}$ the collection of all $A\in\mathcal{A}$ that are at depth $i$ in the decomposition tree, and let $D\triangleq\max\{i\colon\mathcal{A}_{i}\neq\varnothing\}$ denote the maximum depth of an internal (non-leaf) node of the decomposition tree.

Analysis Overview

The goal in analyzing Algorithm 1 is to prove Theorem 1. To this end, two main lemmas are required.

The first lemma provides an upper bound on $\operatorname{val}(\pi)$ , where $\pi$ is the final ordering Algorithm 1 outputs, using only the values of the approximate solutions to all instances of Minimum Submodular $b$ -Balanced Cut computed throughout the entire recursive execution of Algorithm 1. It should be emphasized that this upper bound does not contain values of sets besides the approximate balanced cut solutions, making it easily relatable to $\operatorname{OPT}$ . This is summarized by the following lemma.

Lemma 6.

Let $\pi$ be the ordering Algorithm 1 outputs. Then,

\operatorname{val}(\pi)\leq\sum_{A\in\mathcal{A}}\lvert A\rvert\cdot f\bigl(% \operatorname{Alg}(A)\bigr).

We note that Lemma 6 captures the bulk of the proof of Theorem 1. Moreover, its correctness heavily relies on proving that every prefix $N_{\pi,i}$ corresponds to a different and unique $A\in\mathcal{A}$ and that $N_{\pi,i}$ can be written exactly as a read-once formula using only approximate balanced cut solutions of nodes in the unique path in the decomposition tree between $A$ and the root $N$ .

The second structural lemma provides a lower bound on $\operatorname{OPT}$ using optimal values of disjoint instances of Minimum Submodular $b$ -Balanced Cut, and is independent of Algorithm 1. This is summarized by the following lemma.

Lemma 7.

Let $X_{1},\dots,X_{\ell}\subseteq N$ be pairwise disjoint subsets, and assume that $\lvert X_{i}\rvert\geq 2$ for all $i\in[\ell]$ . For each $i\in[\ell]$ , let $S_{i}^{\star}\subseteq N$ denote an optimal solution to the Minimum Submodular $b$ -Balanced Cut instance $(N,f,w)$ with $w=\mathbf{1}_{X_{i}}$ and $b=\nicefrac{{1}}{{4}}$ . Then,

\sum_{i=1}^{\ell}\lvert X_{i}\rvert\cdot f(S_{i}^{\star})\leq c\cdot% \operatorname{OPT},

for some absolute constant $c>0$ .

Theorem 1 follows from combining Lemmas 6 and 7.

Proof of Theorem 1.

We show that Algorithm 1 satisfies the guarantee of Theorem 1. Let $\pi$ denote the final ordering Algorithm 1 outputs.

Lemma 6 provides the following upper bound on $\operatorname{val}(\pi)$ :

\displaystyle\operatorname{val}(\pi)\leq\sum_{A\in\mathcal{A}}\lvert A\rvert% \cdot f\bigl(\operatorname{Alg}(A)\bigr).

(3.1)

Since $\mathcal{A}=\biguplus_{i=0}^{D}\mathcal{A}_{i}$ , where $\biguplus$ denotes disjoint union, the right-hand side of (3.1) can be rewritten by layers of the decomposition tree as follows:

\displaystyle\sum_{A\in\mathcal{A}}\lvert A\rvert\cdot f\bigl(\operatorname{% Alg}(A)\bigr)=\sum_{i=0}^{D}\sum_{A\in\mathcal{A}_{i}}\lvert A\rvert\cdot f% \bigl(\operatorname{Alg}(A)\bigr).

(3.2)

The contribution of each layer $\mathcal{A}_{i}$ to the right-hand side of (3.2) can be upper bounded by:

\displaystyle\sum_{A\in\mathcal{A}_{i}}\lvert A\rvert\cdot f\bigl(% \operatorname{Alg}(A)\bigr)\leq O\!\left(\sqrt{(\beta^{i}\,n)/(\ln(\beta^{i}n)% )}\right)\cdot\operatorname{OPT},

(3.3)

where $\beta=\nicefrac{{15}}{{16}}$ . To prove (3.3) assume that $\mathcal{A}_{i}=\{A_{1},\dots,A_{\ell}\}$ . For each $j\in[\ell]$ , let $S_{j}^{\star}$ denote an optimal solution to Minimum Submodular $b$ -Balanced Cut for the instance $(N,f,w)$ with $w=\mathbf{1}_{A_{j}}$ and $b=\nicefrac{{1}}{{4}}$ . Since $\operatorname{Alg}(A_{j})$ is obtained by applying Theorem 3 on this instance with $b^{\prime}=\nicefrac{{1}}{{8}}$ :

\displaystyle f\bigl(\operatorname{Alg}(A_{j})\bigr)\leq O\!\left(\sqrt{\lvert A% _{j}\rvert/\ln\lvert A_{j}\rvert}\right)\cdot f(S_{j}^{\star}).

(3.4)

The function $x/\ln x$ is increasing for all $x\geq e$ , and $\lvert A_{j}\rvert\leq\beta^{i}n$ for every $A_{j}\in\mathcal{A}_{i}$ (recall the balancing guarantee of Theorem 3 and the choice of $b^{\prime}=\nicefrac{{1}}{{8}}$ ). Hence,the right-hand side of (3.4) can be further upper bounded as follows:

\displaystyle f\bigl(\operatorname{Alg}(A_{j})\bigr)\leq O\!\left(\sqrt{(\beta% ^{i}\,n)/\ln(\beta^{i}n)}\right)\cdot f(S_{j}^{\star}).

(3.5)

Summing over (3.5) for all $A\in\mathcal{A}_{i}$ and noting that $A_{1},\ldots,A_{\ell}$ are pairwise disjoint by construction, Lemma 7 implies that:

	$\displaystyle\sum_{A\in\mathcal{A}_{i}}\lvert A\rvert\cdot f\bigl(% \operatorname{Alg}(A)\bigr)$	$\displaystyle\leq O\!\left(\sqrt{(\beta^{i}\,n)/\ln(\beta^{i}n)}\right)\sum_{j% =1}^{\ell}\lvert A_{j}\rvert\cdot f(S_{j}^{\star})$
		$\displaystyle\leq O\!\left(\sqrt{(\beta^{i}\,n)/\ln(\beta^{i}n)}\right)\cdot% \operatorname{OPT}.$

Thus, (3.3) holds.

Therefore,

\displaystyle\operatorname{val}(\pi)

\displaystyle\leq\sum_{i=0}^{D}O\!\left(\sqrt{(\beta^{i}\,n)/\ln\bigl(\beta^{i% }\,n\bigr)}\right)\cdot\operatorname{OPT}=O\!\left(\sqrt{n/\ln n}\right)\cdot% \operatorname{OPT},

(3.6)

where: $(1)$ the inequality in (3.6) follows from combining (3.1) and (3.2) and applying (3.3) to each layer $\mathcal{A}_{i}$ ; and $(2)$ the equality in (3.6) follows since by definition, layer $\mathcal{A}_{D}$ contains a subset $A$ with $\lvert A\rvert\geq 2$ and $\lvert A\rvert\leq\beta^{D}n$ , thus implying that $D\leq\ln{(n/2)}/\ln{(1/\beta)}$ . Hence, standard arithmetic (see Lemma 12 in Appendix A) suffices to conclude the proof. $\hfill\blacktriangleleft$

Proving Lemma 6

Lemma 6 is the crux of the proof of Theorem 1, and its proof requires two preliminary steps.

First, the value of the solution is related to the decomposition tree. Specifically, the value of the final ordering $\pi$ produced by Algorithm 1 is expressed as a sum of terms associated with the non-base recursive invocations as follows:

\displaystyle\operatorname{val}(\pi)=\sum_{A\in\mathcal{A}}f\!\left(\left(% \operatorname{Alg}(A)\cap A\right)\cup h(A)\right).

(3.7)

Recall that for any $A\in\mathcal{A}$ , $h(A)\subseteq N$ denotes the set of elements that Algorithm 1 places strictly before $A$ in the final ordering $\pi$ , i.e., elements placed to the left of $A$ in the final ordering $\pi$ .

To see why (3.7) is true, consider a non-base recursive call on a subset $A\in\mathcal{A}$ . Algorithm 1 invokes Theorem 3 and obtains a subset $\operatorname{Alg}(A)\subseteq N$ , and defines $T\leftarrow\operatorname{Alg}(A)\cap A$ . At this point, the algorithm commits to placing all elements of $T$ strictly before, i.e., to the left of, all elements of $A\setminus T$ in the final ordering. Subsequent recursive calls only determine the relative order within $T$ and within $A\setminus T$ , but cannot violate the above ordering constraint. Thus, as a consequence of this commitment, in the final ordering $\pi$ there exists a necessarily unique index $t$ satisfying: $N_{\pi,t}=h(A)\cup T$ . Hence, the recursive call on $A$ corresponds to a unique prefix $N_{\pi,t}$ . Moreover, distinct recursive calls correspond to distinct prefixes, and the associated term $f(N_{\pi,t})$ in the objective can be written as $f\!\left((\operatorname{Alg}(A)\cap A)\cup h(A)\right)$ . Summing the corresponding terms over all $A\in\mathcal{A}$ yields (3.7).

Second, an additional recursive sequence of subsets associated with the execution of the algorithm is needed. To simplify presentation, a mild abuse of notation is introduced, as $A$ is used to denote both an internal (non-leaf) node in the decomposition tree and the set associated with the corresponding recursive call. For a node $A\in\mathcal{A}$ , let $A^{(i)}$ denote the $i$ ^th ancestor of $A$ in the decomposition tree, where $A^{(0)}\triangleq A$ , $A^{(1)}$ is the immediate parent of $A$ , and so on, until reaching the root. Let $d(A)$ denote the depth of $A$ in the decomposition tree, i.e., the unique integer such that $A^{(d(A))}=N$ (recall that $N$ is the root of the decomposition tree).

For a node $A\in\mathcal{A}$ and a set $Z\subseteq N$ , consider the following sequence of subsets whose definition is recursive. The base case is $E_{0}\triangleq Z$ and for $i=1,2,\dots,d(A)$ the recursion is:

E_{i}\triangleq\begin{cases}\operatorname{Alg}\!\bigl(A^{(i)}\bigr)\ \cap\ E_{% i-1},&\text{if }A^{(i-1)}\text{ is a left child of }A^{(i)},\\[4.0pt] \operatorname{Alg}\!\bigl(A^{(i)}\bigr)\ \cup\ E_{i-1},&\text{if }A^{(i-1)}% \text{ is a right child of }A^{(i)}.\end{cases}

The subset of interest, denoted by $T_{A}(Z)$ , is the last subset in the above sequence: $T_{A}(Z)\triangleq E_{d(A)}$ .

The following lemma captures the key structural property of the construction of $T_{A}(Z)$ . It proves that when instantiated with $Z=\operatorname{Alg}(A)$ , the set $T_{A}(Z)$ coincides exactly with the contribution of the prefix that corresponds to the recursive call on $A$ to $\operatorname{val}(\pi)$ (3.7), i.e., $T_{A}(Z)=(\operatorname{Alg}(A)\cap A)\cup h(A)$ . This identity is crucial, as $T_{A}(Z)$ admits by definition a simple read-once formula, implying that $(\operatorname{Alg}(A)\cap A)\cup h(A)$ admits the same read-once formula.

Lemma 8.

For every $A\in\mathcal{A}$ and every $Z\subseteq N$ : $T_{A}(Z)=(Z\cap A)\ \cup\ h(A)$ .

Proof.

We prove the lemma by induction on the depth $d(A)$ of node $A$ in the decomposition tree.

First, consider the base case, i.e., $A=N$ is the root of the decomposition tree with $d(A)=0$ . By definition $T_{N}(Z)=E_{0}=Z$ . Moreover, $h(N)=\varnothing$ implying that $(Z\cap N)\cup h(N)=Z$ . Thus, the lemma holds for the base case.

Second, assume the lemma holds for all nodes in the decomposition tree of depth at most $i$ and let $A$ be a node of depth $i+1$ . Denote the parent of $A$ by $P$ . Consider two cases depending on whether $A$ is a left or right child of $P$ in the decomposition tree.

Assume $A$ is a left child of $P$ , i.e., $A=\operatorname{Alg}(P)\cap P$ by the definition of Algorithm 1. Observe that in this case the definitions of $T_{A}(\cdot)$ and $T_{P}(\cdot)$ imply that:

\displaystyle T_{A}(Z)=T_{P}(\operatorname{Alg}(P)\cap Z).

(3.8)

Applying the induction hypothesis to $P$ yields that: $T_{P}(\operatorname{Alg}(P)\cap Z)=((\operatorname{Alg}(P)\cap Z)\cap P)\cup h% (P)$ . Thus,

\displaystyle T_{P}(\operatorname{Alg}(P)\cap Z)=(A\cap Z)\cup h(P)=(A\cap Z)% \cup h(A),

(3.9)

where: $(1)$ the first equality follows since $A=\operatorname{Alg}(P)\cap P$ ; and $(2)$ the second equality follows since $h(A)=h(P)$ (recalling that $A$ is the left child of $P$ ). Combining (3.8) and (3.9) concludes the proof of the inductive step in the case where $A$ is a left child.

Assume $A$ is a right child of $P$ , i.e., $A=P\setminus(\operatorname{Alg}(P)\cap P)$ by the definition of Algorithm 1. Observe that in this case the definitions of $T_{A}(\cdot)$ and $T_{P}(\cdot)$ imply that:

\displaystyle T_{A}(Z)=T_{P}(\operatorname{Alg}(P)\cup Z).

(3.10)

Applying the induction hypothesis to $P$ yields that: $T_{P}(\operatorname{Alg}(P)\cup Z)=((\operatorname{Alg}(P)\cup Z)\cap P)\cup h% (P)$ . Hence,

$\displaystyle T_{P}(\operatorname{Alg}(P)\cup Z)$	$\displaystyle=((\operatorname{Alg}(P)\cap P)\cup(Z\cap P))\cup h(P)$	(3.11)
	$\displaystyle=((\operatorname{Alg}(P)\cap P)\cup(Z\cap A))\cup h(P)$	(3.12)
	$\displaystyle=(Z\cap A)\cup h(A),$	(3.13)

where: $(1)$ equality (3.11) follows from standard boolean arithmetics, i.e., $(\operatorname{Alg}(P)\cup Z)\cap P=(\operatorname{Alg}(P)\cap P)\cup(Z\cap P)$ ; $(2)$ equality (3.12) follows since $A=P\setminus(\operatorname{Alg}(P)\cap P)$ , implying that $(\operatorname{Alg}(P)\cap P)\cup(Z\cap P)=(\operatorname{Alg}(P)\cap P)\cup(Z% \cap A)$ ; and $(3)$ equality (3.13) follows since $h(A)=h(P)\cup(\operatorname{Alg}(P)\cap P)$ , as the left child of $P$ , namely $\operatorname{Alg}(P)\cap P$ , precedes the right child of $P$ , namely $A$ , in the final ordering. Combining (3.10) and (3.13) concludes the proof of the inductive step in the case where $A$ is a right child. $\hfill\blacktriangleleft$

Equipped with Lemma 8, Lemma 6 can now be proved.

Proof of Lemma 6.

Fix $A\in\mathcal{A}$ and consider its term $f\!\left(\left(\operatorname{Alg}(A)\cap A\right)\cup h(A)\right)$ in (3.7). Applying Lemma 8 with $Z=\operatorname{Alg}(A)$ yields:

\displaystyle f\!\left(\left(\operatorname{Alg}(A)\cap A\right)\cup h(A)\right% )=f\bigl(T_{A}(\operatorname{Alg}(A))\bigr)\leq\sum_{i=0}^{d(A)}f\bigl(% \operatorname{Alg}(A^{(i)})\bigr).

(3.14)

The inequality in (3.14) follows from submodularity and non-negativity of $f$ since both imply that $f(S\cup T)\leq f(S)+f(T)$ and $f(S\cap T)\leq f(S)+f(T)$ for every $S,T\subseteq N$ . Specifically, the recursive definition of $T_{A}(\operatorname{Alg}(A))$ implies that $T_{A}(\operatorname{Alg}(A))$ is obtained via successive union and intersection operations with $\operatorname{Alg}(A^{(0)}),\operatorname{Alg}(A^{(1)}),\ldots,\operatorname{% Alg}(A^{(d(A))})$ , where each $\operatorname{Alg}(A^{(i)})$ appears exactly once in this sequence of operations.

Therefore, plugging (3.14) into (3.7) provides:

\displaystyle\operatorname{val}(\pi)\leq\sum_{A\in\mathcal{A}}\sum_{i=0}^{d(A)% }f\bigl(\operatorname{Alg}(A^{(i)})\bigr).

(3.15)

Observe that in the double sum (3.15), each term $f(\operatorname{Alg}(A))$ is counted once for every node $B\in\mathcal{A}$ such that $A$ is an ancestor of $B$ in the decomposition tree, i.e., for every node contained in the subtree rooted at $A$ . Since Algorithm 1 partitions subsets until reaching singletons, the subtree rooted at $A$ contains exactly $|A|$ leaves. As the decomposition tree is a full binary tree and $\mathcal{A}$ contains only non-leaf nodes, this subtree therefore contains exactly $\lvert A\rvert-1$ internal nodes. Hence, each term $f(\operatorname{Alg}(A))$ appears exactly $\lvert A\rvert-1$ times in the sum. Thus,

\operatorname{val}(\pi)\leq\sum_{A\in\mathcal{A}}(\lvert A\rvert-1)\cdot f% \bigl(\operatorname{Alg}(A)\bigr).

The proof is concluded by observing that $\lvert A\rvert-1\leq\lvert A\rvert$ . $\hfill\blacktriangleleft$

Proving Lemma 7

The proof of the lower bound Lemma 7 provides boils down to the observation that one can choose sufficiently many distinct solutions to the relevant Minimum Submodular $b$ -Balanced Cut instances that correspond to distinct prefixes of an optimal ordering for MLOP.

Proof of Lemma 7.

Let $\pi^{\star}$ be an optimal ordering of $N$ , i.e., $\operatorname{val}(\pi^{\star})=\operatorname{OPT}$ . Recall that:

\displaystyle\operatorname{val}(\pi^{\star})\;=\;\operatorname{OPT}\;=\;\sum_{% t=1}^{n-1}f\!\left(N_{\pi^{\star},t}\right),

(3.16)

where $N_{\pi^{\star},t}$ denotes the prefix of $\pi^{\star}$ consisting of its first $t$ elements: $N_{\pi^{\star},t}=\{u\in N\colon\pi^{\star}(u)\leq t\}$ .

Fix $X_{i}$ for some $i\in[\ell]$ , and for every $j=1,\dots,\lvert X_{i}\rvert$ , let $C_{i,j}\subseteq N$ denote the prefix of $\pi^{\star}$ that contains all elements appearing in $\pi^{\star}$ no later than the $j$ ^th element of $X_{i}$ , where the elements of $X_{i}$ are ordered according to their appearance order in $\pi^{\star}$ . Thus, if the $j$ ^th element of $X_{i}$ with respect to the order $\pi^{\star}$ is $u$ , and $\pi^{\star}(u)=k$ , then $C_{i,j}=N_{\pi^{\star},k}$ .

Let $\mathcal{C}_{i}\;=\;\{C_{i,1},C_{i,2},\dots,C_{i,\lvert X_{i}\rvert}\}$ . Note that each subset $C_{i,j}$ is a distinct prefix of $\pi^{\star}$ and thus corresponds to a distinct cut in the right-hand side of (3.16). Hence,

\displaystyle\sum_{j=1}^{\lvert X_{i}\rvert}f(C_{i,j})\geq\sum_{j=\left\lceil% \lvert X_{i}\rvert/4\right\rceil}^{\left\lfloor 3\lvert X_{i}\rvert/4\right% \rfloor}f(C_{i,j})\geq\sum_{j=\left\lceil\lvert X_{i}\rvert/4\right\rceil}^{% \left\lfloor 3\lvert X_{i}\rvert/4\right\rfloor}f(S_{i}^{\star})\geq\frac{% \lvert X_{i}\rvert}{6}\cdot f(S_{i}^{\star}).

(3.17)

In the above: $(1)$ the first inequality holds since $f$ is nonnegative; $(2)$ the second inequality holds since, for every $j\in\{\lceil\lvert X_{i}\rvert/4\rceil,\dots,\lfloor 3\lvert X_{i}\rvert/4\rfloor\}$ , the subset $C_{i,j}$ contains exactly $j$ elements of $X_{i}$ by construction, and therefore is a feasible solution to the Minimum Submodular $b$ -Balanced Cut instance defined by $(N,f,w)$ with $w=\mathbf{1}_{X_{i}}$ and $b=\nicefrac{{1}}{{4}}$ (implying that $C_{i,j}$ is a feasible solution for the same instance for which $S_{i}^{\star}$ is an optimal solution and thus $f(S_{i}^{\star})\leq f(C_{i,j})$ ); and $(3)$ the third and last inequality holds since $\left\lfloor 3\lvert X_{i}\rvert/4\right\rfloor-\left\lceil\lvert X_{i}\rvert/% 4\right\rceil+1\geq\lvert X_{i}\rvert/6$ whenever $\lvert X_{i}\rvert\geq 2$ .

Since the subsets $X_{1},\dots,X_{\ell}$ are pairwise disjoint, the collections $\mathcal{C}_{1},\dots,\mathcal{C}_{\ell}$ consist of distinct prefixes of $\pi^{\star}$ . Therefore,

\displaystyle\operatorname{OPT}\;=\;\sum_{t=1}^{n-1}f(N_{\pi^{\star},t})\;\geq% \;\sum_{i=1}^{\ell}\sum_{j=1}^{\lvert X_{i}\rvert}f(C_{i,j}).

(3.18)

Combining (3.18) with (3.17) concludes the proof with $c=6$ . $\hfill\blacktriangleleft$

4 Tight Information-Theoretic Hardness

Given an ordering $\pi$ of $N$ , denote by $R_{\pi,i}\triangleq N\setminus N_{\pi,i}=\{u\in N\colon\pi(u)>i\}$ the suffix of length $n-i$ of $\pi$ . Let $\delta>0$ be a parameter to be chosen later and let $\pi$ be a uniformly random ordering of $N$ . Define the following two set functions $f_{1},f_{2}:2^{N}\to\mathbb{R}$ , where $f_{1}$ is deterministic and $f_{2}$ is random, since it depends on $\pi$ :

	$\displaystyle f_{1}(S)$	$\displaystyle\triangleq\min\left\{\lvert S\rvert/2,\|\bar{S}\|/2\right\},$		(4.1)
	$\displaystyle f_{2}(S)$	$\displaystyle\triangleq\min\left\{f_{1}(S),\min\left\{\bigl(i/2+\delta\bigr)+% \lvert S\cap R_{\pi,i}\rvert-\lvert S\rvert/2\;\colon\;i=1,\dots,n-1\right\}% \right\}.$		(4.2)

Intuitively, hiding a random ordering $\pi$ through its suffixes allows $f_{2}$ to include, for each prefix $N_{\pi,i}$ appearing in the MLOP objective, a term with a significantly low value.

$\blacktriangleright$ Remark.

The construction above is inspired by the hardness of Svitkina and Fleischer [37] for Minimum Submodular $b$ -Balanced Cut and the subsequent hardness of $2$ for MLOP given by [24]. In particular, the deterministic function $f_{1}$ (4.1) is identical to the one used in the above earlier results. However, the randomized function $f_{2}$ (4.2) differs from the above results. In both [24, 37], the randomized function hides a single randomized bisection, whereas (4.2) hides an entire random ordering through all of its suffixes.

First, we establish a general lemma that provides a sufficient condition for submodularity that applies to a broad class of set functions, including those used in our hardness construction.

Lemma 9.

Let $U_{m}\subseteq U_{m-1}\subseteq\cdots\subseteq U_{0}\subseteq N$ be a nested family of subsets of $N$ , and let $\alpha_{0},\alpha_{1},\ldots,\alpha_{m}\in\mathbb{R}$ . Define a set function $g\colon 2^{N}\to\mathbb{R}$ as follows:

g(S)\triangleq\min_{0\leq i\leq m}\left\{\alpha_{i}+\lvert S\cap U_{i}\rvert% \right\}.

Then, $g$ is submodular.

Proof.

For every $i\in\{0,\ldots,m\}$ , define $g_{i}\colon 2^{N}\rightarrow\mathbb{R}$ as follows: $g_{i}(S)\triangleq\alpha_{i}+\lvert S\cap U_{i}\rvert$ . Consider the following two observations:

(i)

For every $i\in\{0,\ldots,m\}$ the function $g_{i}$ is submodular: this is true since $g_{i}$ is modular and thus it is also submodular.
(ii)

For every $i<j$ the function $(g_{i}-g_{j})(S)\triangleq g_{i}(S)-g_{j}(S)$ is monotone non-decreasing: this is true since $(g_{i}-g_{j})(S)=(\alpha_{i}-\alpha_{j})+\lvert S\cap(U_{i}\setminus U_{j})\rvert$ as $U_{j}\subseteq U_{i}$ .

We prove that $g(S)$ is submodular by induction on $m$ . The base case is when $m=0$ , implying that: $g=g_{0}$ . Since observation i above implies that $g_{0}$ is submodular, the base case holds.

Focusing on the inductive case of $m>0$ , consider the functions: $\min_{0\leq i\leq m-1}\{g_{i}\}$ and $g_{m}$ . The induction hypothesis implies that $\min_{0\leq i\leq m-1}\{g_{i}\}$ is submodular, and observation i implies that $g_{m}$ is submodular. Moreover, one can note that $\min_{0\leq i\leq m-1}\{g_{i}\}-g_{m}$ is monotone non-decreasing. The reason for the latter is that:

\displaystyle\min_{0\leq i\leq m-1}\{g_{i}\}-g_{m}=\min_{0\leq i\leq m-1}\{g_{% i}-g_{m}\},

(4.3)

and the right-hand side of (4.3) is a point-wise minimum of monotone non-decreasing functions (recalling that observation ii implies that $g_{i}-g_{m}$ is monotone non-decreasing for every $i<m$ ). Therefore, the right-hand side of (4.3) is a monotone non-decreasing function on its own since it is the point-wise minimum of monotone non-decreasing functions.

All the conditions of Lemma 4 are satisfied for the two functions $\min_{0\leq i\leq m-1}\{g_{i}\}$ and $g_{m}$ , implying that $\min\{\min_{0\leq i\leq m-1}\{g_{i}\},g_{m}\}=\min_{0\leq i\leq m}\{g_{i}\}$ is a submodular function. $\hfill\blacktriangleleft$

The following lemma proves that $f_{1}$ and $f_{2}$ , regardless of the outcome of the random choice $\pi$ , are both non-negative and submodular (as required).

Lemma 10.

For every $\delta>0$ and every ordering $\pi$ of $N$ , $f_{1}$ and $f_{2}$ are non-negative and submodular.

Proof of Lemma 10.

We start with $f_{1}$ . By definition (4.1), $f_{1}(S)$ is non-negative. For submodularity, note that $f_{1}$ (4.1) can be equivalently written as:

\displaystyle f_{1}(S)=\min\{|S|,n/2\}-|S|/2.

(4.4)

Both terms in the minimum of (4.4) are of the form $\alpha_{i}+\lvert S\cap R_{\pi,i}\rvert$ : $(1)$ the term $|S|$ corresponds to $i=0$ with $R_{\pi,0}=N$ and $\alpha_{0}=0$ ; $(2)$ the term $n/2$ corresponds to $i=n$ with $R_{\pi,n}=\varnothing$ and $\alpha_{n}=n/2$ . Since $\varnothing=R_{\pi,n}\subseteq R_{\pi,0}=N$ forms a nested chain, all conditions of Lemma 9 are satisfied. This yields that the minimum in (4.4) is a submodular function. Since $|S|/2$ is modular, subtracting it preserves submodularity, and hence $f_{1}$ is submodular.

Let us now focus on $f_{2}$ . Fix any $\delta>0$ and any ordering $\pi$ of $N$ . First, we prove that $f_{2}$ is non-negative. Since $f_{1}$ is non-negative, it suffices to show that for every $i\in\{1,\ldots,n-1\}$ :

\displaystyle\left(i/2+\delta\right)+\lvert S\cap R_{\pi,i}\rvert-|S|/2\geq 0.

(4.5)

Fixing $i$ and substituting $|S|$ with $\lvert S\cap R_{\pi,i}\rvert+\lvert S\cap N_{\pi,i}\rvert$ in (4.5) yields:

	$\displaystyle\left(i/2+\delta\right)+\lvert S\cap R_{\pi,i}\rvert-\lvert S% \rvert/2$	$\displaystyle=\left(i/2+\delta\right)+\lvert S\cap R_{\pi,i}\rvert/2-\lvert S% \cap N_{\pi,i}\rvert/2$
		$\displaystyle\geq i/2-\lvert S\cap N_{\pi,i}\rvert/2.$		(4.6)

The right-hand side of (4.6) is non-negative since $\lvert S\cap N_{\pi,i}\rvert\leq\lvert N_{\pi,i}\rvert=i$ .

Second, we prove that $f_{2}$ is submodular. To this end, note that $f_{2}$ (4.2) can be equivalently written as:

\displaystyle f_{2}(S)

\displaystyle=\min\left\{|S|,n/2,\min\left\{\left(i/2+\delta\right)+|S\cap R_{% \pi,i}|\;\colon\;i=1,\dots,n-1\right\}\right\}-|S|/2.

(4.7)

Each of the $n+1$ terms in the minimum of (4.7) is of the form $\alpha_{i}+|S\cap R_{\pi,i}|$ : $(1)$ the term $|S|$ corresponds to $i=0$ with $R_{\pi,0}=N$ and $\alpha_{0}=0$ ; $(2)$ the term $n/2$ corresponds to $i=n$ with $R_{\pi,n}=\varnothing$ and $\alpha_{n}=n/2$ ; and $(3)$ the remainder of the terms correspond to $i\in\{1,\ldots,n-1\}$ with $R_{\pi,i}$ and $\alpha_{i}=i/2+\delta$ . Noting that $\varnothing=R_{\pi,n}\subseteq R_{\pi,n-1}\subseteq\ldots\subseteq R_{\pi,1}% \subseteq R_{\pi,0}=N$ forms a nested chain, all conditions of Lemma 9 are satisfied. This yields that the minimum in (4.7) is a submodular function. Since $|S|/2$ is modular, subtracting it preserves submodularity, and hence $f_{2}$ is submodular. $\hfill\blacktriangleleft$

The following lemma shows that for a suitable choice of $\delta$ , $f_{1}$ and $f_{2}$ satisfy the probabilistic requirement of the indistinguishability lemma, i.e., Lemma 5. In what follows, recall that $f_{1}$ (4.1) is deterministic whereas $f_{2}$ (4.2) is random and its randomness is determined by a uniform random ordering $\pi$ of $N$ .

Lemma 11.

Assume that $\delta=\omega(\sqrt{n\ln n})$ . Then, for every $S\subseteq N$ : $\Pr_{\pi}[f_{1}(S)\neq f_{2}(S)]\leq n^{-\omega(1)}$ .

Proof.

Fix $S\subseteq N$ . By the definition of $f_{2}$ (4.2):

\displaystyle\Pr\nolimits_{\pi}[f_{1}(S)\neq f_{2}(S)]=\Pr\nolimits_{\pi}\left% [\exists i\in\{1,\ldots,n-1\}:(i/2+\delta)+\lvert S\cap R_{\pi,i}\rvert-\lvert S% \rvert/2<f_{1}(S)\right].

For each $i\in\{1,\ldots,n-1\}$ , let $p_{i}(S)\triangleq\Pr_{\pi}[\bigl(i/2+\delta\bigr)+\lvert S\cap R_{\pi,i}% \rvert-\lvert S\rvert/2<f_{1}(S)]$ . We note that proving, for all $i$ , that $p_{i}(S)\leq n^{-\omega(1)}$ , suffices to conclude the proof. The reason is that the union bound over all possible $i$ gives: $\Pr[f_{1}(S)\neq f_{2}(S)]\leq\sum_{i=1}^{n-1}p_{i}(S)\leq(n-1)\cdot n^{-% \omega(1)}\leq n^{-\omega(1)}$ , as required.

We start by showing that $p_{i}(S)$ is maximized when $\lvert S\rvert=n/2$ . Suppose that $\lvert S\rvert\geq n/2$ . In this case $f_{1}(S)=|\bar{S}|/2$ , and hence:

	$\displaystyle p_{i}(S)$	$\displaystyle=\Pr\nolimits_{\pi}\left[(i/2+\delta)+\lvert S\cap R_{\pi,i}% \rvert-\lvert S\rvert/2<\lvert\bar{S}\rvert/2\right]$
		$\displaystyle=\Pr\nolimits_{\pi}\left[\lvert S\cap R_{\pi,i}\rvert<n/2-(i/2+% \delta)\right].$		(4.8)

Thus, removing an element from $S$ can only increase the probability on the right-hand side of (4.8). Suppose that $\lvert S\rvert\leq n/2$ . In this case, $f_{1}(S)=|S|/2$ , and hence:

\displaystyle p_{i}(S)=\Pr\nolimits_{\pi}\left[(i/2+\delta)+\lvert S\cap R_{% \pi,i}\rvert-\lvert S\rvert/2<\lvert S\rvert/2\right]=\Pr\nolimits_{\pi}\left[% i/2+\delta<\lvert S\cap N_{\pi,i}\rvert\right],

(4.9)

where the last equality follows since $|S\cap R_{\pi,i}\rvert+\lvert S\cap N_{\pi,i}\rvert=\lvert S\rvert$ . Thus, adding an element to $S$ can only increase the probability on the right-hand side of (4.9). Therefore, it suffices to consider sets $S$ of size $n/2$ . Assume henceforth that $\lvert S\rvert=n/2$ .

Focusing on $p_{i}(S)$ , note that $R_{\pi,i}$ is a uniformly random subset of $N$ of size $n-i$ . Hence, the quantity $|S\cap R_{\pi,i}|$ counts how many of these $n-i$ sampled elements belong to $S$ . As $\lvert S\rvert=n/2$ , this corresponds to sampling without replacement from a population consisting of $n/2$ ones (corresponding to elements of $S$ ) and $n/2$ zeros (corresponding to elements of $\bar{S}$ ). By Hoeffding’s inequality for sampling without replacement (see, e.g., [22, 4]),

	$\displaystyle p_{i}(S)$	$\displaystyle=\Pr\nolimits_{\pi}\left[\lvert S\cap R_{\pi,i}\rvert-(n-i)/2<-% \delta\right]\leq\exp\left(-2\delta^{2}/(n-i)\right)$
		$\displaystyle\leq\exp\left(-2\delta^{2}/n\right)\leq n^{-\omega(1)},$

where the last inequality follows since $\delta^{2}/n=\omega(\ln n)$ (recall that $\delta=\omega(\sqrt{n\ln{n}})$ ). This establishes the bound on $p_{i}(S)$ assumed above, and completes the proof. $\hfill\blacktriangleleft$

We are now ready to prove Theorem 2.

Proof of Theorem 2.

Consider MLOP with the two functions $f_{1}$ and $f_{2}$ defined earlier. Throughout this proof, by a slight abuse of notation, we use $f_{2}$ to denote both the random function and an arbitrary fixed realization of it.

First, focus on $f_{1}$ . Let $\operatorname{OPT}_{1}$ denote the optimal value of MLOP with the function $f_{1}$ . For any ordering $\pi$ and any $i\in\{1,\ldots,n-1\}$ : $f_{1}(N_{\pi,i})=\min\{i/2,(n-i)/2\}$ , which depends only on $i$ . Hence, the MLOP objective with $f_{1}$ does not depend on the ordering $\pi$ , yielding:

\displaystyle\operatorname{OPT}_{1}=\sum_{i=1}^{n-1}\min\left\{i/2,(n-i)/2% \right\}\geq n^{2}/16.

Second, consider $f_{2}$ . Fix an arbitrary realization of $f_{2}$ , and let $\operatorname{OPT}_{2}$ denote the optimal value of MLOP with $f_{2}$ . The ordering $\pi$ that defines $f_{2}$ therefore satisfies $\operatorname{OPT}_{2}\leq\sum_{i=1}^{n-1}f_{2}(N_{\pi,i})$ . Note that for every $i\in\{1,\ldots,n-1\}$ : $f_{2}(N_{\pi,i})\leq\delta$ . The reason for the latter is that $N_{\pi,i}\cap R_{\pi,i}=\varnothing$ and $\lvert N_{\pi,i}\rvert=i$ , and thus:

\displaystyle f_{2}(N_{\pi,i})\leq\left(i/2+\delta\right)+\lvert N_{\pi,i}\cap R% _{\pi,i}\rvert-\lvert N_{\pi,i}\rvert/2=\delta.

Therefore, $\operatorname{OPT}_{2}\leq\sum_{i=1}^{n-1}f_{2}(N_{\pi,i})\leq n\delta$ .

We conclude that for all possible realizations of $f_{2}$ :

\displaystyle\operatorname{OPT}_{1}\geq n^{2}/16=\gamma\cdot n\delta\geq\gamma% \cdot\operatorname{OPT}_{2},

(4.10)

where the equality follows from setting $\gamma=n/(16\delta)$ .

Choosing $\delta=\omega(\sqrt{n\ln{n}})$ implies that: $(1)$ the indistinguishability requirement of Lemma 5 is satisfied by Lemma 11 and our choice of $\delta$ ; and $(2)$ the optima ratio requirement of Lemma 5 is satisfied with $\gamma=n/(16\delta)$ (4.10) . Therefore, the two requirements of Lemma 5 are satisfied. Thus, the above and Lemma 10, which establishes that $f_{1}$ and $f_{2}$ are always non-negative and submodular, conclude the proof of the theorem since $\gamma=o(\sqrt{n/\ln{n}})$ . $\hfill\blacktriangleleft$

References

[1] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1–37, 2009. doi:10.1145/1502793.1502794.
[2] Yossi Azar, Iftah Gamzu, and Ran Roth. Submodular max-sat. In European Symposium on Algorithms, pages 323–334. Springer, 2011. doi:10.1007/978-3-642-23719-5_28.
[3] Nikhil Bansal, Jatin Batra, Majid Farhadi, and Prasad Tetali. Improved approximations for min sum vertex cover and generalized min sum set cover. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 998–1005. SIAM, 2021. doi:10.1137/1.9781611976465.62.
[4] Rémi Bardenet and Odalric-Ambrym Maillard. Concentration inequalities for sampling without replacement. arXiv preprint, 2013. arXiv:1309.4029.
[5] 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.
[6] Sandeep N. Bhatt and Frank Thomson Leighton. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci., 28(2):300–343, 1984. doi:10.1016/0022-0000(84)90071-0.
[7] Moses Charikar, Mohammad Taghi Hajiaghayi, Howard Karloff, and Satish Rao. $\ell_{2}^{2}$ spreading metrics for vertex ordering problems. Algorithmica, 56(4):577–604, 2010. doi:10.1007/S00453-008-9191-1.
[8] 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. doi:10.1007/BFB0028251.
[9] Shahar Dobzinski and Jan Vondrák. From query complexity to computational complexity. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1107–1116, 2012. doi:10.1145/2213977.2214076.
[10] Alina Ene, Jan Vondrák, and Yi Wu. Local distribution and the symmetry gap: Approximability of multiway partitioning problems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 306–325. SIAM, 2013. doi:10.1137/1.9781611973105.23.
[11] Guy Even, Joseph Seffi Naor, Satish Rao, and Baruch Schieber. Divide-and-conquer approximation algorithms via spreading metrics. Journal of the ACM (JACM), 47(4):585–616, 2000. doi:10.1145/347476.347478.
[12] Majid Farhadi, Swati Gupta, Shengding Sun, Prasad Tetali, and Michael C Wigal. Hardness and approximation of submodular minimum linear ordering problems. Mathematical Programming, 208(1):277–318, 2024. doi:10.1007/S10107-023-02038-Z.
[13] Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629–657, 2008. doi:10.1137/05064299X.
[14] Uriel Feige and James R Lee. An improved approximation ratio for the minimum linear arrangement problem. Information Processing Letters, 101(1):26–29, 2007. doi:10.1016/J.IPL.2006.07.009.
[15] Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover. Algorithmica, 40(4):219–234, 2004. doi:10.1007/S00453-004-1110-5.
[16] Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133–1153, 2011. doi:10.1137/090779346.
[17] Yuval Filmus, Roy Schwartz, and Alexander V Smal. Separating coverage and submodular: Maximization subject to a cardinality constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 242–255. Springer, 2025. doi:10.1007/978-3-031-93112-3_18.
[18] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1098–1116. SIAM, 2011. doi:10.1137/1.9781611973082.83.
[19] Gagan Goel, Chinmay Karande, Pushkar Tripathi, and Lei Wang. Approximability of combinatorial problems with multi-agent submodular cost functions. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 755–764. IEEE Computer Society, 2009. doi:10.1109/FOCS.2009.81.
[20] Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. Approximating submodular functions everywhere. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 535–544. SIAM, 2009. doi:10.1137/1.9781611973068.59.
[21] Refael Hassin and Asaf Levin. An approximation algorithm for the minimum latency set cover problem. In European Symposium on Algorithms, pages 726–733. Springer, 2005. doi:10.1007/11561071_64.
[22] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830.
[23] Satoru Iwata and Kiyohito Nagano. Submodular function minimization under covering constraints. In 2009 50th annual IEEE symposium on foundations of computer science, pages 671–680. IEEE, 2009. doi:10.1109/FOCS.2009.31.
[24] Satoru Iwata, Prasad Tetali, and Pushkar Tripathi. Approximating minimum linear ordering problems. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 206–217. Springer, 2012. doi:10.1007/978-3-642-32512-0_18.
[25] Dor Katzelnick and Roy Schwartz. A simple algorithm for submodular minimum linear ordering. In Symposium on Simplicity in Algorithms (SOSA), pages 28–35. SIAM, 2023. doi:10.1137/1.9781611977585.CH3.
[26] 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. doi:10.1145/331524.331526.
[27] Yixun Lin and Jinjiang Yuan. Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica, 10:107–112, 1994. doi:10.1007/BF02006264.
[28] László Lovász. Submodular functions and convexity. In Mathematical Programming The State of the Art: Bonn 1982, pages 235–257. Springer, 1983. doi:10.1007/978-3-642-68874-4_10.
[29] Vahab Mirrokni, Michael Schapira, and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the 9th ACM conference on Electronic commerce, pages 70–77, 2008. doi:10.1145/1386790.1386805.
[30] 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. doi:10.1287/MOOR.3.3.177.
[31] G. Ramalingam and C.Pandu Rangan. A unified approach to domination problems on interval graphs. Information Processing Letters, 27(5):271–274, 1988. doi:10.1016/0020-0190(88)90091-9.
[32] Satish Rao and Andréa W Richa. New approximation techniques for some linear ordering problems. SIAM Journal on Computing, 34(2):388–404, 2005. doi:10.1137/S0097539702413197.
[33] Ramamurthy Ravi, Ajit Agrawal, and Philip Klein. Ordering problems approximated: single-processor scheduling and interval graph completion. In International Colloquium on Automata, Languages, and Programming, pages 751–762. Springer, 1991. doi:10.1007/3-540-54233-7_180.
[34] Richard Santiago and F Bruce Shepherd. Multivariate submodular optimization. In International Conference on Machine Learning, pages 5599–5609. PMLR, 2019. URL: http://proceedings.mlr.press/v97/santiago19a.html.
[35] Paul D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995. doi:10.1007/BF01200760.
[36] 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. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.50.
[37] Zoya Svitkina and Lisa Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM Journal on Computing, 40(6):1715–1737, 2011. doi:10.1137/100783352.
[38] Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265–304, 2013. doi:10.1137/110832318.

Appendix A Missing Proofs: Algorithm 1

Lemma 12.

Let $\beta\in(0,1)$ be a fixed constant and let $D\leq\nicefrac{{\ln(n/2)}}{{\ln(1/\beta)}}$ . Then,

\sum_{i=0}^{D}\sqrt{\frac{\beta^{i}\,n}{\ln(\beta^{i}\,n)}}=O\!\left(\sqrt{% \frac{n}{\ln n}}\right).

Proof.

From the assumption on $D$ , we have $\beta^{D}n\geq 2$ , and since $0<\beta<1$ , this implies $\beta^{i}n\geq 2$ for all $0\leq i\leq D$ , hence $\ln(\beta^{i}n)\geq\ln 2$ .

Let

I:=\left\lfloor\frac{\ln n}{2\ln(1/\beta)}\right\rfloor.

Then $\beta^{I}n\geq\sqrt{n}$ and $\beta^{I+1}n\leq\sqrt{n}$ .

For $0\leq i\leq\min\{I,D\}$ , we have $\ln(\beta^{i}n)\geq\ln(\beta^{I}n)\geq\tfrac{1}{2}\ln n$ , and therefore

\sqrt{\frac{\beta^{i}n}{\ln(\beta^{i}n)}}\leq\sqrt{\frac{2n}{\ln n}}\,\bigl(% \sqrt{\beta}\bigr)^{i}.

Summing and using that $\beta$ is constant,

\sum_{i=0}^{\min\{I,D\}}\sqrt{\frac{\beta^{i}n}{\ln(\beta^{i}n)}}\leq\sqrt{% \frac{2n}{\ln n}}\sum_{i=0}^{\infty}(\sqrt{\beta})^{i}=O\!\left(\sqrt{\frac{n}% {\ln n}}\right).

If $D>I$ , then for $i\geq I+1$ we have $\beta^{i}n\leq\beta^{I+1}n\leq\sqrt{n}$ and $\ln(\beta^{i}n)\geq\ln 2$ , hence

\sqrt{\frac{\beta^{i}n}{\ln(\beta^{i}n)}}\leq\sqrt{\frac{n}{\ln 2}}\,(\sqrt{% \beta})^{i}.

Thus,

\sum_{i=I+1}^{D}\sqrt{\frac{\beta^{i}n}{\ln(\beta^{i}n)}}\leq\sqrt{\frac{n}{% \ln 2}}\sum_{i=I+1}^{\infty}(\sqrt{\beta})^{i}=O\!\left(n^{1/4}\right)=o\!% \left(\sqrt{\frac{n}{\ln n}}\right).

Combining the two parts yields the claim. $\hfill\blacktriangleleft$

[bib.bib1] [1] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1–37, 2009. doi:10.1145/1502793.1502794.

[bib.bib2] [2] Yossi Azar, Iftah Gamzu, and Ran Roth. Submodular max-sat. In European Symposium on Algorithms, pages 323–334. Springer, 2011. doi:10.1007/978-3-642-23719-5_28.

[bib.bib3] [3] Nikhil Bansal, Jatin Batra, Majid Farhadi, and Prasad Tetali. Improved approximations for min sum vertex cover and generalized min sum set cover. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 998–1005. SIAM, 2021. doi:10.1137/1.9781611976465.62.

[bib.bib4] [4] Rémi Bardenet and Odalric-Ambrym Maillard. Concentration inequalities for sampling without replacement. arXiv preprint, 2013. arXiv:1309.4029.

[bib.bib5] [5] 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.

[bib.bib6] [6] Sandeep N. Bhatt and Frank Thomson Leighton. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci., 28(2):300–343, 1984. doi:10.1016/0022-0000(84)90071-0.

[bib.bib7] [7] Moses Charikar, Mohammad Taghi Hajiaghayi, Howard Karloff, and Satish Rao. $\ell_{2}^{2}$ spreading metrics for vertex ordering problems. Algorithmica, 56(4):577–604, 2010. doi:10.1007/S00453-008-9191-1.

[bib.bib8] [8] 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. doi:10.1007/BFB0028251.

[bib.bib9] [9] Shahar Dobzinski and Jan Vondrák. From query complexity to computational complexity. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1107–1116, 2012. doi:10.1145/2213977.2214076.

[bib.bib10] [10] Alina Ene, Jan Vondrák, and Yi Wu. Local distribution and the symmetry gap: Approximability of multiway partitioning problems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 306–325. SIAM, 2013. doi:10.1137/1.9781611973105.23.

[bib.bib11] [11] Guy Even, Joseph Seffi Naor, Satish Rao, and Baruch Schieber. Divide-and-conquer approximation algorithms via spreading metrics. Journal of the ACM (JACM), 47(4):585–616, 2000. doi:10.1145/347476.347478.

[bib.bib12] [12] Majid Farhadi, Swati Gupta, Shengding Sun, Prasad Tetali, and Michael C Wigal. Hardness and approximation of submodular minimum linear ordering problems. Mathematical Programming, 208(1):277–318, 2024. doi:10.1007/S10107-023-02038-Z.

[bib.bib13] [13] Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629–657, 2008. doi:10.1137/05064299X.

[bib.bib14] [14] Uriel Feige and James R Lee. An improved approximation ratio for the minimum linear arrangement problem. Information Processing Letters, 101(1):26–29, 2007. doi:10.1016/J.IPL.2006.07.009.

[bib.bib15] [15] Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover. Algorithmica, 40(4):219–234, 2004. doi:10.1007/S00453-004-1110-5.

[bib.bib16] [16] Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133–1153, 2011. doi:10.1137/090779346.

[bib.bib17] [17] Yuval Filmus, Roy Schwartz, and Alexander V Smal. Separating coverage and submodular: Maximization subject to a cardinality constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 242–255. Springer, 2025. doi:10.1007/978-3-031-93112-3_18.

[bib.bib18] [18] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1098–1116. SIAM, 2011. doi:10.1137/1.9781611973082.83.

[bib.bib19] [19] Gagan Goel, Chinmay Karande, Pushkar Tripathi, and Lei Wang. Approximability of combinatorial problems with multi-agent submodular cost functions. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 755–764. IEEE Computer Society, 2009. doi:10.1109/FOCS.2009.81.

[bib.bib20] [20] Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. Approximating submodular functions everywhere. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 535–544. SIAM, 2009. doi:10.1137/1.9781611973068.59.

[bib.bib21] [21] Refael Hassin and Asaf Levin. An approximation algorithm for the minimum latency set cover problem. In European Symposium on Algorithms, pages 726–733. Springer, 2005. doi:10.1007/11561071_64.

[bib.bib22] [22] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830.

[bib.bib23] [23] Satoru Iwata and Kiyohito Nagano. Submodular function minimization under covering constraints. In 2009 50th annual IEEE symposium on foundations of computer science, pages 671–680. IEEE, 2009. doi:10.1109/FOCS.2009.31.

[bib.bib24] [24] Satoru Iwata, Prasad Tetali, and Pushkar Tripathi. Approximating minimum linear ordering problems. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 206–217. Springer, 2012. doi:10.1007/978-3-642-32512-0_18.

[bib.bib25] [25] Dor Katzelnick and Roy Schwartz. A simple algorithm for submodular minimum linear ordering. In Symposium on Simplicity in Algorithms (SOSA), pages 28–35. SIAM, 2023. doi:10.1137/1.9781611977585.CH3.

[bib.bib26] [26] 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. doi:10.1145/331524.331526.

[bib.bib27] [27] Yixun Lin and Jinjiang Yuan. Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica, 10:107–112, 1994. doi:10.1007/BF02006264.

[bib.bib28] [28] László Lovász. Submodular functions and convexity. In Mathematical Programming The State of the Art: Bonn 1982, pages 235–257. Springer, 1983. doi:10.1007/978-3-642-68874-4_10.

[bib.bib29] [29] Vahab Mirrokni, Michael Schapira, and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the 9th ACM conference on Electronic commerce, pages 70–77, 2008. doi:10.1145/1386790.1386805.

[bib.bib30] [30] 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. doi:10.1287/MOOR.3.3.177.

[bib.bib31] [31] G. Ramalingam and C.Pandu Rangan. A unified approach to domination problems on interval graphs. Information Processing Letters, 27(5):271–274, 1988. doi:10.1016/0020-0190(88)90091-9.

[bib.bib32] [32] Satish Rao and Andréa W Richa. New approximation techniques for some linear ordering problems. SIAM Journal on Computing, 34(2):388–404, 2005. doi:10.1137/S0097539702413197.

[bib.bib33] [33] Ramamurthy Ravi, Ajit Agrawal, and Philip Klein. Ordering problems approximated: single-processor scheduling and interval graph completion. In International Colloquium on Automata, Languages, and Programming, pages 751–762. Springer, 1991. doi:10.1007/3-540-54233-7_180.

[bib.bib34] [34] Richard Santiago and F Bruce Shepherd. Multivariate submodular optimization. In International Conference on Machine Learning, pages 5599–5609. PMLR, 2019. URL: http://proceedings.mlr.press/v97/santiago19a.html.

[bib.bib35] [35] Paul D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995. doi:10.1007/BF01200760.

[bib.bib36] [36] 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. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.50.

[bib.bib37] [37] Zoya Svitkina and Lisa Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM Journal on Computing, 40(6):1715–1737, 2011. doi:10.1137/100783352.

[bib.bib38] [38] Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265–304, 2013. doi:10.1137/110832318.

Tight Algorithm and Hardness for Submodular Linear Ordering

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Value-Oracle Model

1.1 Our Result

Theorem 1.

Theorem 2.

1.2 Our Techniques

Algorithmic Approach

Hardness Approach

1.3 Related Work

Paper Organization

2 Preliminaries

Submodular 𝒃-Balanced Cut

Theorem 3 (Svitkina and Fleischer [37]).

Submodularity Preserving Operations

Lemma 4 (Lovász [28]).

Indistinguishability

Lemma 5 (Svitkina and Fleischer [37]).

3 𝑶⁢(𝒏/𝐥𝐧⁡𝒏)-Approximation Algorithm

Analysis Notations

Analysis Overview

Lemma 6.

Lemma 7.

Proof of Theorem 1.

Proving Lemma 6

Lemma 8.

Proof.

Proof of Lemma 6.

Proving Lemma 7

Proof of Lemma 7.

4 Tight Information-Theoretic Hardness

▶ Remark.

Lemma 9.

Proof.

Lemma 10.

Proof of Lemma 10.

Lemma 11.

Proof.

Proof of Theorem 2.

References

Appendix A Missing Proofs: Algorithm 1

Lemma 12.

Proof.

Submodular $𝒃$ -Balanced Cut

3 $O\left(\sqrt{n/\ln{n}}\right)$ -Approximation Algorithm

$\blacktriangleright$ Remark.