Semidefinite and linear programming integrality gaps for scheduling identical machines

Abstract

Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász and Schrijver (SIAM J Optim 1:166–190, 1991) developed systematic procedures to construct the hierarchies of relaxations known as lift-and-project methods. They have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. Then we show that for any integer n there is an instance with n jobs in this family such that after $\varOmega (n)$ rounds of the Sherali–Adams ($\text {SA}$) or the Lovász–Schrijver ($\text {LS}_+$) hierarchy the integrality gap remains at least 1024/1023.

1 Introduction

1.1 Scheduling

Machine scheduling is a classical family of problems in combinatorial optimization. In this paper we study the problem, known as $P||C_{\max }$, of scheduling a set J of n jobs on a set M of identical machines to minimize the makespan, i. e., the maximum completion time of a job, where each job $j\in J$ has a processing time $p_{j}$. A job cannot be preempted nor migrated to a different machine, and every job is released at time zero. This problem admits a polynomial-time approximation scheme (PTAS) [17] and even an EPTAS [2], which is the best possible approximation result since the problem is strongly $\mathsf {NP}$-hard [13]. However, there is no algorithm known based on convex relaxations that meets the results in [2] and [17].

Assignment LP A straightforward way to model $P||C_{\max }$ with a linear program (LP) is the assignment LP which has a variable $x_{ij}$ for each combination of a machine $i\in M$ and a job $j\in J$, modeling whether job j is assigned to machine i. The goal is to minimize a variable T (modeling the makespan) for which we require that $\sum _{j\in J}x_{ij}\cdot p_{j}\le T$ for each machine i.

Configuration LP The assignment LP is dominated by the configuration LP which is, to the best of our knowledge, the strongest relaxation for the problem studied in the literature. Suppose we are given a value $T>0$ that is an estimate on the optimal makespan, e. g., given by a binary search framework. A configuration corresponds to a multiset of processing times $C\subseteq \{ p_j: j\in J\}$ such that $\sum _{p\in C}p\le T$, i. e., it is a feasible assignment for a machine when the time availability is equal to T. Let, for given T, $\mathcal {C}$ denotes the set of all feasible configurations. The multiplicity function m(p, C) indicates the number of times that the processing time p appears in the multiset C. For each combination of a machine i and a configuration C the configuration LP has a variable $y_{iC}$ that models whether we want to assign exactly jobs with processing times in configuration C to machine i. Letting $n_p$ denote the number of jobs $j\in J$ with processing time $p_j=p$, we can write:

We remark that in another common definition [29], a configuration is a subset, not of processing times but of jobs. We can solve that LP to a $(1+\epsilon )$-accuracy in polynomial time [29] and similarly our LP above. The definition in terms of multisets makes sense since we are working in a setting of identical machines.

Integrality gap The configuration LP $\text {clp}(T)$ does not have an objective function and instead we seek to determine the smallest value T for which it is feasible. In this context, for a convex relaxation K(T) we define the integrality gap to be the supremum value $T_{\text {opt}}(I)/T^{*}(I)$ over all problem instances I, where $T_{\text {opt}}(I)$ is the optimal value to the underlying combinatorial problem and $T^{*}(I)$ is the minimum value T for which K(T) is feasible. With the additional constraint that $T\ge \max _{j\in J}p_{j}$, the Assignment LP relaxation has an integrality gap of 2. This can be shown using the analysis of the list scheduling algorithm, see e. g., [30]. On the other hand a lower bound of $2-1/|M|$ can be easily shown for the instance of $|M|+1$ jobs of unit size. Here we prove that the configuration LP has an integrality gap of at least 1024/1023 (Theorem 1(i)).

1.2 Linear programming and semi-definite programming hierarchies

Hierarchies An interesting question is whether other convex relaxations have better integrality gaps. Convex hierarchies, parametrized by a number of levels or rounds, are systematic approaches to design improved approximation algorithms by gradually tightening the relaxation, at the cost of increased running time. Popular among these methods are the Sherali–Adams (SA) hierarchy [27] (Definition 1), the Lovász–Schrijver hierarchy ($\text {LS}$) and its semi-definite counterpart ($\text {LS}_+$) [23], (Definition 4) and the Lasserre/Sum-Of-Squares hierarchy [20, 24], which is the strongest of the three. The level r relaxations are known to be solvable in time $n^{O(r)}$, where n is the number of variables, provided some assumptions over the ground polytope. In particular, when r is constant, the complexity of solving the relaxation becomes polynomial on the program size. This is relevant when looking for an approximation algorithm based on this relaxation. For a comparison between them and their algorithmic implications we refer to [11, 21, 25]. In some settings, for example the Independent Set problem in sparse graphs [5], a mixed SA has also been considered.

Positive results For many problems the approximation factors of the best algorithms known match the integrality gap after performing a constant number of rounds of these hierarchies. For example, Alekhnovich, Arora, and Tourlakis [1] show that one round of $\text {LS}_+$ yields the Goemans-Williamson [15] relaxation for Max-Cut, and the third level of $\text {LS}_+$ is at least as strong as the ARV relaxation for Sparsest-Cut [4]. In both cases, the base relaxation over which the hierarchy is applied corresponds to the metric defining linear program. Also for Max-Cut, Fernandez de la Vega and Mathieu [28] prove that the integrality gap of the SA hierarchy drops to $1+\varepsilon$ after $f(1/\varepsilon )$ rounds for dense graphs. For general constraint satisfaction problems (CSP) in its approximation version, Chan et al. [8] show that polynomial-sized linear programs are as powerful as programs arising from constant rounds of SA. In that sense, this hierarchy captures the best integrality gaps obtained by linear programming in CSP’s like Max-Cut and Max-3-Sat. For the Knapsack problem, Chlamtac, Friggstad, and Georgiou [10] show that $1/\varepsilon ^{3}$ levels of $\text {LS}_+$ yield an integrality gap of $1+\varepsilon$ and prove that it is possible to approximate Set-Cover using the linear relaxations of LS when the objective function is lifted into the constraints. In the scheduling context, for minimizing the makespan on two machines in the setting of unit size jobs and precedence constraints, Svensson solves the problem optimally with only one level of the linear LS hierarchy (published in [25, Section 3.1], personal communication between Svensson and the author of [25]). Furthermore, for a constant number of machines, Levey and Rothvoss give a $(1+\varepsilon )$-approximation algorithm using $(\log (n))^{\varTheta (\log \log n)}$ rounds of SA hierarchy [22]. For minimizing weighted completion time on unrelated machines, one round of $\text {LS}_+$ leads to the current best algorithm [6]. Thus, hierarchies are a strong tool for approximation algorithms.

Negative results Nevertheless, there are known limitations on these hierarchies. Lower bounds on the integrality gap of $\text {LS}_+$ are known for Independent Set [12], Vertex Cover [3, 9, 14, 26], Max-3-Sat and Hypergraph Vertex Cover [1], and k-Sat [7]. For the Max-Cut problem, there are lower bounds for the SA [28] and $\text {LS}_+$ [26]. For the Min-Sum scheduling problem (i. e., scheduling with job dependent cost functions on one machine) the integrality gap is unbounded even after $O(\sqrt{n})$ rounds of Lasserre [19]. In particular, that holds for the problem of minimizing the number of tardy jobs even though that problem is solvable in polynomial time, thus SDP hierarchies sometimes fail to reduce the integrality gap even on easy problems.

1.3 Our results

Our key question in this paper is: is it possible to obtain a polynomial time $(1+\epsilon )$-approximation algorithm based on applying the SA or the $\text {LS}_+$ hierarchy to one of the known LP-formulations of our problem? This would match the best known (polynomial time) approximation factor we know [2, 17].

We answer this question in the negative. We prove that even after $\varOmega (n)$ rounds of SA or $\text {LS}_+$ to the configuration LP, where n is the number of jobs in the instance, the integrality gap of the resulting relaxation is still at least $1+1/1023$. Since the configuration LP dominates¹ the assignment LP, our result also holds if we apply $\varOmega (n)$ rounds of SA or $\text {LS}_+$ to the assignment LP.

Theorem 1

Consider the problem of scheduling identical machines to minimize the makespan, $P||C_{\max }$. For each $n\in \mathbb {N}$ there exists an instance with n jobs such that:

• (i) the configuration LP has an integrality gap of at least 1024/1023.

• (ii) after applying $r=\varOmega (n)$ rounds of the SA hierarchy to the configuration LP the obtained relaxation has an integrality gap of at least 1024/1023.

• (iii) after applying $r=\varOmega (n)$ rounds of the $\text {LS}_+$ hierarchy to the configuration LP the obtained relaxation has an integrality gap of at least 1024/1023.

Since polynomial time approximations schemes are known [2, 17] for $P||C_{\max }$, Theorem 1 implies that the $\text {SA}$ and the $\text {LS}_+$ hierarchies do not yield the best possible approximation algorithms. We remark that for the hierarchies studied in Theorem 1, a number of rounds equal to the number of variables in $\text {clp}(T)$ suffice to bring the integrality gap down to exactly 1.

We prove Theorem 1 by defining a family of instances $\{I_{k}\}_{k\in \mathbb {N}}$ constructed from the Petersen graph (see Fig. 1). The size of instance $I_k$, given by the number of machines and jobs, is $\varTheta (k)$ and the number of jobs is $\varTheta (k)$ as well. In Sect. 2 we prove that the configuration LP is feasible for $T=1023$ while the integral optimum has a makespan of at least 1024. In Sect. 3, we show for each instance $I_{k}$ that using the hypergeometric distribution we can define a fractional solution that is feasible for the polytope obtained by applying $\varOmega (k)$ rounds of SA to the configuration LP parametrized by $T=1023$. In Sect. 4 we prove the same for the semidefinite relaxations obtained with the $\text {LS}_+$ hierarchy, and we study the matrices arising in the lower bound proof.

1.4 The hard instances

To prove the integrality gaps of 1024/1023, for each odd $k\in \mathbb {N}$ we define an instance $I_{k}$ that is inspired by the Petersen graph G (see Fig. 1) with vertex set $V=\{ 0,1,\cdots ,9 \}$. For each edge $e=\{u,v\}$ of G, in $I_{k}$ we introduce k copies of a job $j_{\{uv\}}$ of size $2^{u}+2^{v}$. Thus $I_{k}$ has 15k jobs. (If n is not an odd multiple of 15, let $n=15k+\ell$ where k is the greatest odd integer such that $15k<n$. In this case we simply add to the instance $\ell$ jobs that each have processing time equal to zero.) We define the number of machines for $I_k$ to be 3k. For simplicity, in the following we do not distinguish between jobs and their sizes. The graph G has exactly six perfect matchings $\bar{M}_{1},\bar{M}_{2},\cdots ,\bar{M}_{6}$. Since the sum of the job sizes in a perfect matching $\bar{M}_{\ell }$ is

$$\begin{aligned} \sum _{e\in \bar{M}_{\ell }}p_{j_{e}}=\sum _{0\le u\le 9}2^u=1023, \end{aligned}$$

$\bar{M}_{\ell }$ corresponds to a configuration $C_{\ell }$ that contains one job corresponding to each edge in $\bar{M}_{\ell }$ and has makespan 1023. The configurations $C_1,\ldots ,C_6$ are called matching configurations and we denote them by $\mathcal {D}=\{C_1,\ldots ,C_6\}$.

Fig. 1

The Petersen graph and its six perfect matchings (dashed lines)

2 Integrality gap of the configuration LP (Theorem 1(i))

Lemma 1

$\text {clp}[1023]$ is feasible for $I_k$.

Proof

To define the fractional solution, for every machine i and each $\ell \in \{1,2,\cdots ,6\}$ we set $y_{iC_{\ell }}=1/6$. For all other configurations C we set $y_{iC}=0$.

The first set of constraints in clp(T) (for the machines) is clearly satisfied. For the second set of constraints (for the job sizes), let p be such a job size and let e be the corresponding edge in G. The Petersen graph is such that there are exactly two perfect matchings $\bar{M}_{\ell },\bar{M}_{\ell '}$ containing e, thus we get $\sum _{i=1}^{3k} (y_{iC_{\ell }}+y_{iC_{\ell '}})=k$ and y is feasible. $\square$

Lemma 2

The optimal makespan for $I_k$ is at least 1024.

Proof

Assume, for a contradiction, that $\text {clp}[1023]$ for $I_k$ has an integer solution y. Since the total size of jobs is $k\cdot 3 \cdot 1023$ and there are 3k machines, only configurations C with makespan exactly equal to 1023 may have $y_{iC}\ne 0$. In particular, the optimal integral makespan for $I_k$ is at least 1023.

Consider such a configuration C. Since $1023=\sum _{u=0}^9 2^u$, considering the binary representation of 1023, by induction on u it must be that for every u, configuration C contains an odd number of jobs corresponding to edges adjacent to vertex u in G. Furthermore, since the sum does not exceed 1023, that odd number must be exactly 1. Thus C exactly corresponds to a perfect matching of G, and so the integer solution y corresponds to a 1-factorization of the multigraph $G_{k}$ obtained by taking k copies of each edge in the Petersen graph.

Let $\bar{M}_{1}$ be the perfect matching of the Petersen graph consisting of the five edges $\{0,5\},\{1,6\},\{2,7\},\{3,8\}\{4,9\}$, called spokes. Let $\ell =\sum _i y_{iC_1}$. Since each spoke, which appears in exactly one other perfect matching $\bar{M}_{j}$ ($j>1$), must be contained in k matchings in total, we must have $\sum _i y_{iC_j}=k-\ell$ for each $j\in [2,6]$. Thus $\sum _{i,C}y_{iC}=5(k-\ell )+\ell =5k-4\ell .$ However, that sum equals 3k, the total number of machines, and so $\ell =k/2$. Since k is odd and $\ell$ an integer, the contradiction follows. $\square$

3 Integrality gap for $\text {SA}$ (Theorem 1(ii))

We show that for the family of instances $\{I_{k}\}_{k\in \mathbb {N}}$ defined in Sect. 2, if we apply O(k) rounds of SA to the configuration LP for $T=1023$, then the resulting relaxation is feasible. Thus, after $\varOmega (k)$ rounds of SA the configuration LP still has an integrality gap of at least 1024/1023 on an instance with O(k) jobs and machines. First, we define the polytope $\text {SA}^{r}(P)$ obtained after r rounds of SA to a polytope P that is defined via equality constraints.²

Definition 1

(Polytope $\text {SA}^{r}(P)$) Consider a polytope $P\subseteq [0,1]^E$ defined by equality constraints. For every constraint $\sum _{i\in E}a_{i,\ell }y_{i}= b_{\ell }$ and every $H \subseteq E$ such that $|H|\le r$, the constraint $\sum _{i\in E}a_{i, \ell }y_{H\cup \{i\}} = b_{\ell }y_{H}$ is included in $\text {SA}^{r}(P)$, the level r of the Sherali–Adams hierarchy applied to P. The polytope $\text {SA}^{r}(P)$ lives in $\mathbb {R}^{\mathcal {P}_{r+1}(E)}$, where $\mathcal {P}_{r+1}(E)=\{A\subseteq E:|A|\le r+1\}$.

For the configuration LP $\text {clp}(T)$ the variables set is $E=M\times \mathcal {C}$. Since it is defined by equality constraints, the polytope $\text {SA}^{r}(\text {clp}(T))$ corresponds to

Intuitively, the configuration LP computes a set of edges in a complete bipartite graph with vertex sets U, V where U is the set of machines and V is the set of configurations. The edges are selected such that they form a U-matching, i.e., such that each node in U is incident to at most one selected edge.

Definition 2

Given two sets U, V and $F\subseteq U\times V$, the F-degree of $u\in U$ is $\delta _{F}(u)=|\{v:(u,v)\in F\}|$, and $\delta _{F}(v)=|\{u:(u,v)\in F\}|$ if $v\in V$. We say that F is an U-matching if $\delta _{F}(u)\le 1$ for every $u\in U$. An element $u\in U$ is incident to F if $\delta _{F}(u)=1$.

In the following we consider the family of instances $\{I_{k}:k\in \mathbb {N},k\text { is odd}\}$ as in Sect. 2 and $T=1023$. For any set S we define $\mathcal {P}(S)$ to be the power set of S. We want to define a solution to $\text {SA}^{r}(\text {clp}(T))$ for $T=1023$. To this end, we need to define a value $y_{A}$ for each set $A\in \mathcal {P}_{r+1}(M\times \mathcal {C})$. These values are given by the function $\phi$ defined below.

Definition 3

Let $\phi :{\mathcal {P}}(M\times \mathcal {D})\rightarrow \mathbb {R}$ be such that

$$\begin{aligned} \phi (A)=\frac{1}{(3k)_{|A|}}\prod _{j\in [6]}(k/2)_{\delta _{A}(C_{j})} \end{aligned}$$

if A is an M-matching, and zero otherwise, where $(x)_{a}=x(x-1)\cdots (x-a+1)$, for integer $a \ge 1$, is the lower factorial function.

To get some understanding about how the $\phi$ works, the following lemma intuitively shows the following: suppose that we know that a set A is chosen (i.e., we condition on this), then the conditional probability that also a pair $(i,C_{j})$ is chosen equals $\frac{k/2-\delta _{A}(C_{j})}{3k-|A|}$, assuming that $A\cup \{(i,C_{j})\}$ forms an M-matching.

Lemma 3

Let $A\subseteq M\times \mathcal {D}$ be an M-matching of size at most $3k-1$. If $i\in M$ is not incident to A, then $\phi (A\cup \{(i,C_{j})\})=\phi (A)\frac{k/2-\delta _{A}(C_{j})}{3k-|A|}$.

Proof

Given that i is not incident to A, we have $|A\cup \{(i,C_{j})\}|=|A|+1$. Furthermore, for $\ell \ne j$ we have that $\delta _{A\cup \{(i,C_{j})\}}(C_{\ell })=\delta _{A}(C_{\ell })$ and $\delta _{A\cup \{(i,C_{j})\}}(C_{j})=\delta _{A}(C_{j})+1$. Therefore, $\frac{\phi (A\cup \{(i,C_{j})\})}{\phi (A)}=\frac{k/2-\delta _{A}(C_{j})}{3k-|A|}.$ $\square$

The feasible solution We are ready now to define our solution to $\text {SA}^{r}(\text {clp}(T))$. It is the vector $y^{\phi }\in \mathbb {R}^{\mathcal {P}_{r+1}(E)}$ defined such that $y_A^{\phi }=\phi (A)$ if A is an M-matching in $M\times \mathcal {D}$, and zero otherwise.

Lemma 4

For every odd k, $y^{\phi }$ is a feasible solution for $\text {SA}^{r}(\text {clp}(T))$ for the instance $I_{k}$ when $r=\lfloor k/2\rfloor$ and $T=1023$.

Proof

We first prove that $y^{\phi }\ge 0$. Consider some $H\subseteq E$. Since $y^{\phi }_H=\phi (H)$, using Definition 3, it is easy to check that the lower factorial stays non-negative for $r=\lfloor k/2\rfloor$.

We next prove that $y^{\phi }$ satisfies the machine constraints (2) in $\text {SA}^r(\text {clp})$. If i is a machine incident to H, then all terms in the left-hand summation are 0 except for the unique pair (i, C) that belongs to H, so the sum equals $y^{\phi }_{H}$. If i is not incident to H, then by Lemma 3 we have

$$\begin{aligned} \sum _{C}y^{\phi }_{H \cup \{(i,C)\}} = \frac{\phi (H)}{3k-|H|}\sum _{j\in [6]}(k/2-\delta _H(C_j)) = \phi (H) = y^{\phi }_H, \end{aligned}$$

since $6\cdot k/2=3k$ and $\sum _{j\in [6]}\delta _H(C_j)=|H|$.

Finally we prove that $y^{\phi }$ satisfies the set of constraints (3) for every processing time. Fix p and H. Since $y^{\phi }$ is supported by six configurations, we have

$$\begin{aligned} \sum _{i\in M} \sum _{C\in \mathcal {C}}m(p,C)y^{\phi }_{H\cup \{(i,C)\}}= \sum _{i\in M}\sum _{j\in [6]} m(p,C_j)\phi (H\cup \{(i,C_j)\}). \end{aligned}$$

There are exactly two configurations $C_1^p,C_2^p\in \mathcal {D}$ such that

$$\begin{aligned} m(p,C_1^p) = m(p,C_2^p) = 1, \end{aligned}$$

and for the others it is zero, so

$$\begin{aligned} \sum _{j\in [6]} m(p,C_j)\phi (H\cup \{(i,C_j)\})=\phi \left( H\cup \{(i,C_1^p)\}\right) +\phi \left( H\cup \{(i,C_2^p)\}\right) . \end{aligned}$$

Let $\pi _M(H)=\{i\in M:\delta _H(i)=1\}$ be the subset of machines incident to H. We split the sum over $i\in M$ into two parts, $i\in \pi _M(H)$ and $i\notin \pi _M(H)$. For the first part,

$$\begin{aligned} \sum _{i\in \pi _M(H)}(\phi (H\cup \{(i,C_1^p)\})+\phi (H\cup \{(i,C_2^p)\})) =\phi (H)(\delta _H(C_1^p)+\delta _H(C_2^p)) \end{aligned}$$

since $\phi (H\cup \{(i,C_1^p)\})$ is either $\phi (H)$ or 0 depending on whether $(i,C_1^p)\in H$, and the same holds for $C_2^p$.

For the second part, using Lemma 3 we have that

$$\begin{aligned}&\sum _{i\notin \pi _M(H)}\left( \phi (H\cup \{(i,C_1^p)\})+\phi (H\cup \{(i,C_2^p)\})\right) \\&\quad =\frac{\phi (H)}{3k-|H|}\sum _{i\notin \pi _M(H)} (k/2-\delta _H(C_1^p)+k/2-\delta _H(C_2^p))\\&\quad =\phi (H)(k/2-\delta _H(C_1^p)+k/2-\delta _H(C_2^p)), \end{aligned}$$

since $|H\setminus \pi _M(H)|=3k-|H|$. Thanks to cancellations, we get precisely what we want by adding:

$$\begin{aligned} \sum _{i\in M} \sum _{C\in \mathcal {C}} m(p,C)y^{\phi }_{H\cup \{(i,C)\}}=k\phi (H) = n_py_H^{\phi }. \end{aligned}$$

$\square$

Proof of Theorem 1(ii)

Consider instance $I_k$ as defined before, $T=1023$ and $r=\lfloor k/2 \rfloor$. By Lemma 4 the vector $y^{\phi }\in \text {SA}^r(\text {clp}(T))$. $\square$

We note that in the above proof, the projection of $y^\phi$ onto the space of the configuration LP is the fractional solution from the proof of Lemma 1.

4 Integrality gap for $\text {LS}_+$ (Theorem 1(iii))

Given a polytope $P\subseteq \mathbb {R}^{d}$, we consider the convex cone $Q=\{(a,x)\in \mathbb {R}^*\times P:x/a\in P\}$. We define an operator $N_+$ on convex cones $R\subseteq \mathbb {R}^{d+1}$ as follows: $y\in N_+(R)$ if and only if there exists a symmetric matrix $Y\subseteq \mathbb {R}^{(d+1)\times (d+1)}$, called the protection matrix of y, such that

• 1. $y=Ye_{\emptyset }=\text {diag}(Y)$,

• 2. for all i, $Ye_i,Y(e_{\emptyset }-e_i)\in R$,

• 3. Y is positive semidefinite,

where $e_i$ denotes the vector with a 1 in the ith coordinate and 0’s elsewhere.

Definition 4

For any $r\ge 0$ and polytope $P\subseteq \mathbb {R}^{d}$, level r of the $\hbox {LS}_+$ hierarchy, $N_+^r(Q)\subseteq \mathbb {R}^{d+1}$, is defined recursively by: $N_+^0(Q)=Q$ and $N_+^r(Q)=N_+(N_+^{r-1}(Q))$.

To prove the integrality gap for $\text {LS}_+$ we follow an inductive argument. We start from $P=\text {clp}(T)$. Along the proof, we use a special type of vectors that are integral in a subset of coordinates and fractional in the others.

The feasible solution. Let A be an M-matching in $M\times \mathcal {D}$. The partial schedule $y(A)\in \mathbb {R}^{M\times \mathcal {C}}$ is the vector such that for every $i\in M$ and $j\in \{1,2,\cdots ,6\}$, $y(A)_{iC_j}=\phi (A\cup \{(i,C_j)\})/\phi (A)$, and zero otherwise. Here is the key Lemma.

Lemma 5

Let k be an odd integer and $r\le \lfloor k/2 \rfloor$. Let $Q_k$ be the convex cone of $\text {clp}(T)$ for instance $I_k$ and $T=1023$. Then, for every M-matching A of cardinality $\lfloor k/2 \rfloor -r$ in $M\times \mathcal {D}$, we have $y(A)\in N_+^r(Q_k)$.

Before proving Lemma 5, let us see how it implies the Theorem.

Proof of Theorem 1(iii)

Consider instance $I_k$ defined in Sect. 2, $T=1023$ and $r=\lfloor k/2 \rfloor$. By Lemma 5 for $A=\emptyset$ we have $y(\emptyset )\in N_+^r(Q_k)$. $\square$

In the following two helper lemmas we describe structural properties of every partial schedule.

Lemma 6

Let A be an M-matching in $M\times \mathcal {D}$, and let i be a machine incident to A. Then, $y(A)_{iC}\in \{0,1\}$ for all configuration C.

Proof

If $C\notin \mathcal {D}$ then $y(A)_{iC}=0$ by definition. If $(i,C_j)\in A$ then $y(A)_{iC_j}=\phi (A\cup \{(i,C_j)\})/\phi (A)=\phi (A)/\phi (A)=1$. For $\ell \ne j$, the set $A\cup \{(i,C_{\ell })\}$ is not an M-matching and thus $y(A)_{iC_k}=0$.$\square$

Lemma 7

Let A be an M-matching in $M\times \mathcal {D}$ of cardinality at most $\lfloor k/2\rfloor$. Then, $y(A)\in \text {clp}(T)$.

Proof

We note that $y(A)_{iC}=y^{\phi }_{A\cup \{(i,C)\}}/y^{\phi }_A$, and then the feasibility of y(A) in $\text {clp}(T)$ is implied by the feasibility of $y^{\phi }$ in $\text {SA}^r(\text {clp}(T))$, for $r=\lfloor k/2 \rfloor$. $\square$

Given a partial schedule y(A), let $Y(A)\in \mathbb {R}^{(|M\times \mathcal {C}|+1)\times (|M\times \mathcal {C}|+1)}$ be the matrix such that its principal submatrix indexed by $\{\emptyset \}\cup (M\times \mathcal {D})$ equals

$$\begin{aligned} \begin{pmatrix}1 &{}\quad y(A)^{\top }\\ y(A) &{}\quad Z(A)\end{pmatrix}, \end{aligned}$$

where $Z(A)_{iC_j,\ell C_h}=\phi (A\cup \{(i,C_j),(\ell ,C_h)\})/\phi (A)$. All the other entries of the matrix Y(A) have value equal to zero. The matrix Y(A) provides the protection matrix we need in the proof of the key Lemma.

Theorem 2

For every M-matching A in $M\times \mathcal {D}$ such that $|A|\le \lfloor k/2 \rfloor$, the matrix Y(A) is positive semidefinite.

We postpone the proof of Theorem 2 to Sect. 4.1.

Lemma 8

Let A be an M-matching in $M\times \mathcal {D}$ and i a non-incident machine to A. Then, $\sum _{j\in [6]}Y(A)e_{iC_j}=Y(A)e_{\emptyset }.$

Proof

Let S be the index of a row of Y(A). If $S\notin \{0\}\cup (M\times \mathcal {D})$ then that row is identically zero, so the equality is satisfied. Otherwise,

$$\begin{aligned} e_S^{\top }\sum _{j\in [6]}Y(A)e_{iC_j}=\sum _{j\in [6]}\frac{\phi (A\cup \{(i,C_j)\}\cup S)}{\phi (A)}. \end{aligned}$$

If $A\cup S$ is not an M-matching then $\phi (A\cup S\cup \{i,C_j\})=0$ for all i and $j\in [6]$, and $e_S^{\top }Y(A)e_{\emptyset }=\phi (A\cup S)=0$, so the equality is satisfied. If $A\cup S$ is an M-matching, then

$$\begin{aligned} \sum _{j\in [6]}\frac{\phi (A\cup \{(i,C_j)\}\cup S)}{\phi (A)}&=\frac{\phi (A\cup S)}{\phi (A)}\sum _{j\in [6]}\frac{\phi (A\cup S\cup \{(i,C_j)\})}{\phi (A\cup S)} \\&=e_S^{\top }Y(A)e_{\emptyset }\sum _{j\in [6]}\frac{y^{\phi }_{A\cup S\cup \{(i,C_j)\}}}{y^{\phi }_{A\cup S}}\\&=e_S^{\top }Y(A)e_{\emptyset }, \end{aligned}$$

since $y^{\phi }$ is a feasible solution for the $\text {SA}$ hierarchy. $\square$

Having previous two results we are ready to prove the key Lemma.

Proof of Lemma 5

We proceed by induction in r. The base case $r=0$ is implied by Lemma 7, and now suppose that it is true for $r=t$. Let y(A) be a partial schedule of A of cardinality $\lfloor k/2 \rfloor -t-1$. We prove that the matrix Y(A) is a protection matrix for y(A). It is symmetric by definition, $y(A)e_{\emptyset }=\text {diag}(y(A))=y(A)$ and thanks to Theorem 2 the matrix Y(A) is positive semidefinite. Let (i, C) be such that $y(A)_{iC}\in (0,1)$. In particular, by Lemma 6 we have $(i,C)\notin A$ and $C\in \mathcal {D}$. We claim that $Y(A)e_{iC}/y(A)_{iC}$ is equal to the partial schedule $(1,y(A\cup \{(i,C)\}))$. If S indexes a row not in $M\times \mathcal {D}$ then the respective entry in both vectors is zero, so the equality is satisfied. Otherwise,

$$\begin{aligned} \frac{e_S^{\top }Y(A)e_{iC}}{y(A)_{iC}}=\frac{\phi (A\cup \{(i,C)\}\cup S)}{\phi (A\cup \{(i,C)\})}=y(A\cup \{(i,C)\})_S. \end{aligned}$$

The cardinality of the M-matching $A\cup \{(i,C)\}$ is equal to $|A|+1=\lfloor k/2 \rfloor -t$, and therefore by induction we have that $Y(A)e_{iC}/y(A)_{iC}=(1,y(A\cup \{(i,C)\}))\in N_+^t(Q_k)$. Now we prove that the vectors $Y(A)(e_{\emptyset }-e_{iC})/(1-y(A)_{iC})$ are feasible for $N^t_+(Q_k)$. By Lemma 8 we have that for every $\ell \in \{1,2,\cdots ,6\}$,

$$\begin{aligned} \frac{Y(A)(e_{\emptyset }-e_{iC_{\ell }})}{1-y(A)_{iC_{\ell }}}=\sum _{j\in [6]\setminus \{\ell \}}\left( \frac{y(A)_{iC_j}}{\sum _{j\in [6]\setminus \{\ell \}}y(A)_{iC_j}}\right) y(A\cup \{(i,C_j)\}), \end{aligned}$$

and then $Y(A)(e_{\emptyset }-e_{iC_{\ell }})/(1-y(A)_{iC_{\ell }})$ is a convex combination of the partial schedules $\{y(A\cup \{(i,C_j)\}):j\in \{1,2,\cdots ,6\}\setminus \{\ell \}\}\subset N_+^t(Q_k)$, concluding the induction. $\square$

4.1 The matrix Y(A) is positive semidefinite

In this section we provide a full proof of Theorem 2. To prove that Y(A) is a positive semidefinite matrix we perform several transformations of the original matrix that preserve the property of being positive semidefinite or not.

We start with a short summary of the proof. We prove that Y(A) is positive semidefinite by performing several transformations that preserve this property. First, we remove all those zero columns and rows. Then, Y(A) is positive semidefinite if and only if its principal submatrix indexed by $\{\emptyset \}\cup (M\times \mathcal {D})$ is positive semidefinite. We then construct the matrix $\text {Cov}(A)$ by taking the Schur’s Complement of Y(A) with respect to the entry $(\{\emptyset \},\{\emptyset \})$. The resulting matrix is positive semidefinite if and only if Y(A) is positive semidefinite. After removing null rows and columns in $\text {Cov}(A)$ we obtain a new matrix, $\text {Cov}_+(A)$, which can be written using Kronecker products as $I\otimes Q+(J-I)\otimes W$, with $Q,W\in \mathbb {R}^{6\times 6}$, $Q=\alpha W$ for some $\alpha \in (-1,0)$ and I, J being the identity and the all-ones matrix, respectively. By applying a lemma about block matrices in [16], Y(A) is positive semidefinite if and only if W is positive semidefinite. The matrix W is of the form $D_u-uu^{\top }$, with $u\in \mathbb {R}^6$ and $D_u$ is a diagonal matrix such that $\text {diag}(D_u)=u$. By Jensen’s inequality with the function $t(y)=y^2$ it follows that W is positive semidefinite.

We now continue with the full argument.

Lemma 9

A symmetric matrix $X\in \mathbb {R}^{E\times E}$ is psd if and only if the principal submatrix of non-null columns and rows is psd.

Proof

Let $\tilde{X}\in \mathbb {R}^{F\times F}$ be the matrix obtained by removing the null rows and columns of x. Then, $z^{\top }Xz=\sum _{i,j\in E}X_{ij}z_iz_j=\sum _{i,j\in F}X_{ij}z_iz_j=z_F^{\top }\tilde{X}z_{F}$, where $z_F\in \mathbb {R}^F$ is the restriction of Z to the variables in F. It follows that $z^{\top }Xz\ge 0$ if and only if $z_F^{\top }\tilde{X}z_{F}$. $\square$

Therefore, in order to prove that a matrix is positive semidefinite we can remove in advance those null rows and columns. In the following Lemma we describe the next transformation, based on a congruent transformation of a matrix known as Schur’s complement.

Lemma 10

Let $X=\begin{pmatrix}N&{}B\\ B^{\top } &{}C\end{pmatrix}$ be a symmetric matrix, with N invertible. The Schur’s complement of N in X is the matrix $S=C-B^{\top }N^{-1}B$. If N is positive definite, then X is positive semidefinite if and only if S is positive semidefinite.

A proof of this fact can be found in [18, Theorem 7.7.9 on p. 496]. We apply the previous transformations to Y(A) as described in the following lemma.

Lemma 11

For every partial schedule y(A), the matrix Y(A) is positive semidefinite if and only if $Z(A) - y(A)y(A)^{\top }$ is positive semidefinite, where

$$\begin{aligned} Z(A)_{iC_j,\ell C_h}=\phi (A\cup \{(i,C_j),(\ell ,C_h)\})/\phi (A). \end{aligned}$$

Proof

Thanks to Lemma 9 the matrix Y(A) is positive semidefinite if and only if its principal submatrix indexed by $\{\emptyset \}\cup \{M\times \mathcal {D}\}$ is positive semidefinite, since every other row and column is null. The Schur’s complement of the entry $Y(A)_{\emptyset ,\emptyset }=1$ corresponds to $Z(A)-y(A)y(A)^{\top }$. By a direct application of Lemma 10 it follows that Y(A) is positive semidefinite if and only if $Z(A)-y(A)y(A)^{\top }$ is positive semidefinite. $\square$

We denote by $\text {Cov}(A)$ the matrix $Z(A)-y(A)y(A)^{\top }$, the covariance matrix of y(A). In the proof of Lemma 11 we removed first all those null rows and columns in Y(A). In fact, in the new matrix $\text {Cov}(A)$ there are null rows and columns that can be removed of the matrix, so we can perform this operation again.

Lemma 12

Let $\text {Cov}_+(A)$ be the principal submatrix of $\text {Cov}(A)$ obtained by removing every row and column indexed by $E(\pi _M(A))=\{(i,C_j):i\in \pi _M(A),j\in \{1,2,\cdots ,6\} \}$. Then, Y(A) is positive semidefinite if and only if $\text {Cov}_+(A)$ is positive semidefinite.

Proof

Recall that $\pi _M(A)$ is the set of machines incident to A. We prove that for every $(i,C_j)\in E(\pi _M(A))$, $\text {Cov}(A)e_{iC_j}=0$. By the definition of the covariance matrix we have

$$\begin{aligned} e_{\ell C_k}^{\top }\text {Cov}(A)e_{iC_j}=\frac{\phi (A\cup \{(\ell ,C_k),(i,C_j)\})}{\phi (A)}-y(A)_{iC_j} y(A)_{\ell C_k}. \end{aligned}$$

By Lemma 6, if i is an incident machine to A we have $y(A)_{iC_j}=1_{\{(i,C_j)\in A\}}$, and by the definition of the function $\phi$ we have that it is supported over M-matchings only. Then, $\phi (A\cup \{(\ell ,C_k),(i,C_j)\})=\phi (A\cup (\ell ,C_k)\})1_{\{(i,C_j)\in A\}}$, and

$$\begin{aligned} e_{\ell C_k}^{\top }\text {Cov}(A)e_{iC_j}=\left( \frac{\phi (A\cup \{(\ell ,C_k)\})}{\phi (A)}-y(A)_{\ell C_k}\right) 1_{\{(i,C_j)\in A\}}=0, \end{aligned}$$

because of the definition of the partial schedule y(A). The Lemma follows by a direct application of Lemma 9. $\square$

Note that if i is not an incident machine to A, the value $y(A)_{iC_j}$ does not depend on the machine. This motivates the definition of a vector $\beta (A)\in \mathbb {R}^6$ such that

$$\begin{aligned} \beta (A)_j=\frac{k/2-\delta _A(C_j)}{3k-|A|}, \end{aligned}$$

for $j\in \{1,2,\cdots ,6\}$. If y(A) is a partial schedule, for every machine incident to A the entries $y_{iC_j}$ are in $\{0,1\}$, which is in total 3|A| entries.

Definition 5

Let $A\in \mathbb {R}^{p\times q}$ and $B\in \mathbb {R}^{r\times s}$. Then, the Kronecker product, $A\otimes B$, is the matrix

$$\begin{aligned} \begin{pmatrix}a_{11}B &{} \cdots &{} a_{1q}B\\ \vdots &{} \ddots &{} \vdots \\ a_{p1}B &{} \cdots &{} a_{pq}B \end{pmatrix}\in \mathbb {R}^{pr\times qs}. \end{aligned}$$

Then, the fractional part of y(A) corresponds to $\mathbf {1}\otimes \beta (A)$, where $\mathbf {1}$ is the vector in $\mathbb {R}^{3k-|A|}$ with every entry equal to 1. Furthermore, the value $Z(A)_{iC_j,\ell C_{\ell }}=\gamma (A)_{j\ell }$ is independent of the machines when $i,\ell$ are not incident to A,

$$\begin{aligned} \gamma (A)_{j\ell }={\left\{ \begin{array}{ll}\displaystyle \frac{(k/2-\delta _A(j))(k/2-\delta _A(\ell ))}{(3k-|A|)(3k-|A|-1)}&{} \text { if }j\ne \ell ,\\ \\ \displaystyle \frac{(k/2-\delta _A(j))(k/2-\delta _A(j)-1)}{(3k-|A|)(3k-|A|-1)}&{} \text { if }j= \ell . \end{array}\right. } \end{aligned}$$

Then, we can express the matrix $\text {Cov}_+(A)$ in terms of Kronecker products,

$$\begin{aligned} I\otimes D_\beta (A)+(J-I)\otimes \gamma (A) -(\mathbf {1}\otimes \beta (A))(\mathbf {1}\otimes \beta (A))^{\top }, \end{aligned}$$

(6)

where I is the $(3k-|A|)$ dimensional identity matrix, J is the $(3k-|A|)$ dimensional all-ones matrix and $D_{\beta }(A)\in \mathbb {R}^{6\times 6}$ is such that $D_{\beta }(A)_{jj}=\beta (A)_j$ for $j\in \{1,\ldots ,6\}$, and $D_{\beta }(A)_{jh}=0$ when $j\ne h$.

Definition 6

A matrix $X\in \mathbb {R}^{rn\times rn}$ belongs to the (r, n)-block symmetry set $\mathcal {BS}(r,n)$ if there exist matrices $A,B\in \mathbb {R}^{r\times r}$ such that $X=I\otimes A+(J-I)\otimes B$, namely,

$$\begin{aligned} X=\begin{pmatrix}A&{}\quad B&{}\quad \cdots &{}\quad B\\ B&{}\quad A&{}\quad \cdots &{}\quad B\\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ B&{}\quad B&{}\quad \cdots &{}\quad A \end{pmatrix}. \end{aligned}$$

Lemma 13

(Gvozdenovic and Laurent [16]) Let $X=I\otimes A+(J-I)\otimes B\in \mathcal {BS}(r,n)$. Then, X is positive semidefinite if and only if i) $A-B$ is positive semidefinite and ii) $A+(n-1)B$ is positive semidefinite.

Previous lemma characterizes the subset of positive semidefinite matrices for $\mathcal {BS}(r,n)$. In particular, the following lemma proves that $\text {Cov}_+(A)$ belongs to a block symmetry set by using (6).

Lemma 14

For every M-matching A in $M\times \mathcal {D}$, the covariance matrix $\text {Cov}_+(A)$ belongs to $\mathcal {BS}(3k-|A|,6)$ and it is equal to

$$\begin{aligned} I\otimes \varDelta (A)-(J-I)\otimes \frac{1}{3k-|A|-1}\varDelta (A), \end{aligned}$$

where $\varDelta (A)=D_{\beta }(A)-\beta (A)\beta (A)^{\top }.$

Proof

By expanding the Kronecker product we can see that

$$\begin{aligned} (\mathbf {1}\otimes \beta (A))(\mathbf {1}\otimes \beta (A))^{\top }=J\otimes (\beta (A)\beta (A)^{\top }). \end{aligned}$$

Replacing this in the expression in (1) we get

$$\begin{aligned} \text {Cov}_+(A)&=I\otimes D_{\beta }(A)+(J-I)\otimes \gamma (A) -J\otimes (\beta (A)\beta (A)^{\top })\\&=I\otimes D_{\beta }(A)-\beta (A)\beta (A)^{\top })+(J-I)\otimes (\gamma (A)-\beta (A)\beta (A)^{\top })\\&=I\otimes \varDelta (A)+(J-I)\otimes (\gamma (A)-\beta (A)\beta (A)^{\top }). \end{aligned}$$

This proves that $\text {Cov}(A)_+\in \mathcal {BS}(3k-|A|,6)$. It remains to check that $\gamma (A)-\beta (A)\beta (A)^{\top }=-\varDelta (A)/(3k-|A|-1)$. Consider two configurations $C_j\ne C_{\ell }$. Then, a non diagonal element is equal to

$$\begin{aligned} \gamma (A)_{j\ell }-\beta (A)_j\beta (A)_{\ell }&=\frac{(k/2-\delta _A(j))(k/2-\delta _A(\ell ))}{(3k-|A|)(3k-|A|-1)}-\beta (A)_j\beta (A)_{\ell }\\&=\frac{3k-|A|}{3k-|A|-1}\beta (A)_j\beta (A)_{\ell }-\beta (A)_j\beta (A)_{\ell }\\&=\frac{1}{3k-|A|-1}\beta (A)_j\beta (A)_{\ell }\\&=-\frac{1}{3k-|A|-1}\varDelta (A)_{j\ell }. \end{aligned}$$

For a diagonal element, we have

$$\begin{aligned} \gamma (A)_{jj}-\beta (A)_j^2&=\frac{(k/2-\delta _A(j))(k/2-\delta _A(j)-1)}{(3k-|A|)(3k-|A|-1)}-\beta (A)_j^2\\&=\frac{3k-|A|}{3k-|A|-1}\left( \beta (A)_j^2-\frac{1}{3k-|A|}\beta (A)_j\right) -\beta (A)_j^2\\&=-\frac{1}{3k-|A|-1}(\beta (A)_j-\beta (A)_j^2)\\&=-\frac{1}{3k-|A|-1}\varDelta (A)_{jj}. \end{aligned}$$

$\square$

In addition with Lemma 13 we have the ingredients to prove that $\text {Cov}_+(A)$ is a positive semidefinite matrix when $|A|\le \lfloor k/2 \rfloor$.

Proof of Theorem 2

By Lemma 14, $\text {Cov}_+(A)\in \mathcal {BS}(3k-|A|,6)$ and then we can apply Lemma 13. Therefore, the matrix $\text {Cov}_+(A)$ is positive semidefinite if and only if i) $\varDelta (A)-\frac{1}{3k-|A|-1}\varDelta (A)=\frac{3k-|A|}{3k-|A|-1}\varDelta (A)$ is positive semidefinite, and ii) $\varDelta (A)-(3k-|A|-1)\cdot \frac{1}{3k-|A|-1}\varDelta (A)=0$ is positive semidefinite. The last condition is trivially satisfied, and then $\text {Cov}_+(A)$ is positive semidefinite if and only if $\varDelta (A)$ is positive semidefinite. Given any vector $x\in \mathbb {R}^6$, we have

$$\begin{aligned} x^{\top }\varDelta (A)x=\sum _{j=1}^6\beta (A)_jx_j^2-\left( \sum _{j=1}^6\beta (A)_jx_j\right) ^2. \end{aligned}$$

The vector $\beta (A)\in \mathbb {R}^6$ is non-negative if $|A|\le \lfloor k/2 \rfloor$. As it satisfies that $\Vert \beta (A)\Vert _1=1$, by applying Jensen’s inequality with the function $\phi (w)=w^2$ the latter expression is non-negative for every $x\in \mathbb {R}^6$. Then, $\text {Cov}_+(A)$ is positive semidefinite, and thanks to Lemma 12 we conclude that Y(A) is positive semidefinite. $\square$

5 Discussion

What happens if we try to extend the results of Theorem 1?

Other hierarchies One obvious open problem is whether the Lasserre hierarchy is any more successful for $P||C_{\max }$. The family of instances $\{I_k\}$ used in our proofs of Theorems 1(ii) and (iii) may or may not be useful. A proof of feasibility requires proving that a matrix derived from the $\text {SA}$ solution is positive semi-definite. However, it is unclear for the authors how to handle the calculations for that case.

Other basic relaxations We also do not know the integrality gap of the hierarchies if we use variants of the basic LP relaxation $\text {clp}$, for example, when a configuration is a set of jobs (instead of a multiset of processing times) and the constraints guaranteeing that each job is assigned are equality constraints, one for each job (instead of inequality constraints, one for each processing time).

Other scheduling problems What about a related scheduling problem that is even simpler than $P||C_{\max }$, namely, when the number m of machines is fixed? This problem is denoted $Pm||C_{\max }$. We consider the $\text {LS}$ linear hierarchy, defined in the same way that $\text {LS}_+$, but the requirement of having a positive semidefinite protection matrix is removed. The following theorem tells that a number of rounds equal to number of machines are enough to reach the convex hull of the integral solutions for the scheduling problem $P||C_{\max }$.

Theorem 3

The relaxation obtained by applying a number of rounds of $\text {LS}$ equal to the number of machines over the configuration LP has an integrality gap of 1.

Proof

Let $\mathcal {S}$ be the set of integer solutions in $\text {clp}(T)$ and let m be the number of machines in the scheduling instance. Let $y\in N^m(\text {clp}(T))$ and (i, C) such that $0<y_{iC}<1$. Then, there exists a protection matrix Y such that $Ye_0=\text {diag}(Y)=y$, and $Ye_{iC}/y_{iC},Y(e_0-e_{iC})/(1-y_{iC})\in N^{m-1}(\text {clp}(T))$. Then, y can be written as

$$\begin{aligned} y=y_{iC}\cdot \frac{Ye_{iC}}{y_{iC}}+(1-y_{iC})\cdot \frac{Y(e_0-e_{iC})}{1-y_{iC}}, \end{aligned}$$

and $Ye_{iC}/y_{iC},Y(e_0-e_{iC})/(1-y_{iC})$ are integral on variable (i, C). Furthermore, these vectors are integral for every variable (i, L) with $L\in \mathcal {C}$, since $\sum _{L\in \mathcal {C}}y_{iL}=1$. If the vectors are not integral, we repeat this step on each vector by selecting a new fractional variable. We notice that after applying the step the set of fractional variables is the same for every vector in the convex combination, and then the same fractional variable can be taken for all of them. As a consequence, every time we perform this step at least one machine is scheduled integrally. Therefore, we perform at most m steps until we reach a convex combination of integral vectors. $\square$

Corollary 1

Consider the problem of scheduling identical machines to minimize the makespan $Pm||C_{\max }$ wth a fixed number of machines. Then, applying $r=O(1)$ rounds of $\text {LS}$ hierarchy to the configuration LP $\text {clp}$, the relaxation obtained, $N^r(\text {clp})$, has an integrality gap equal to 1.

In particular, as $\text {LS}$ is the weakest of all hierarchies, this result also holds for $\text {SA}$ and $\text {LS}_+$.

On the other hand, for the harder problem of scheduling to minimize makespan on unrelated machines, $R||C_{\max }$, the best known algorithm is a 2-approximation, matching the best known integrality gap of a relaxation (the configuration LP), whereas the strongest lower bound is 3/2. Is it possible that one of the LP or SDP hierarchies starting from the configuration LP gives an integrality gap strictly less than 2? This would open the way to designing an improved approximation algorithms for $R||C_{\max }$, a major open question.