A Linear Programming Approach to the Rectangular Covering Problem: Duality and Lower Bounds

Introduction

The rectangular covering problem asks for the smallest number $k$ of axis‑aligned rectangles needed to cover an $n\times n$ grid of unit squares such that each row and each column contains exactly one uncovered square. Equivalently, choose a permutation $\sigma$ of $\{0,\dots ,n-1\}$ and partition the complement of the permutation matrix ${(i,\sigma(i))\}$ into $k$ rectangles, each rectangle being a product $I\times J$ of a contiguous set $I$ of rows and a contiguous set $J$ of columns with $\sigma(I)\cap J=\varnothing$. Denote by $R(n)$ the minimum possible $k$, minimized over $\sigma$ and over all rectangle packings.

It is conjectured that $R(n)=n+\big\lfloor\frac{n-1}{2}\big\rfloor$. A recursive construction attains this number of rectangles for every $n$, proving $R(n)\le n+\lfloor(n-1)/2\rfloor$. A matching lower bound has so far resisted proof. In this note we propose a linear‑programming approach that may lead to such a lower bound.

Integer linear programming formulation

For a fixed permutation $\sigma$, let $\mathcal R$ be the family of all allowed rectangles (those that avoid the forbidden squares). Introduce a binary variable $x_R$ for each $R\in\mathcal R$ indicating whether $R$ is used in the covering. The requirement that every covered cell $(i,j)$ (with $j\neq\sigma(i)$) belongs to exactly one rectangle is expressed as

[ \sum_{R\ni(i,j)} x_R = 1 \qquad\text{for all allowed cells }(i,j). ]

The objective is to minimise $\sum_{R\in\mathcal R} x_R$. This is an integer linear program (ILP).

Linear programming relaxation and its dual

Relaxing $x_R\ge0$ gives a linear program (LP) whose optimal value $\mathrm{LP}(\sigma)$ is a lower bound on the number of rectangles needed to cover $\sigma$. By strong duality, $\mathrm{LP}(\sigma)$ equals the optimal value of the dual LP, which reads

[ \begin{aligned} \text{maximise}\quad & \sum_{\substack{i,j\\ j\neq\sigma(i)}} w_{ij} \\[2pt] \text{subject to}\quad & \sum_{(i,j)\in R} w_{ij}\le 1 \qquad\text{for all }R\in\mathcal R,\\[2pt] & w_{ij}\ge 0 \qquad\text{for all allowed cells }(i,j). \end{aligned} ]

Thus we have to assign non‑negative weights $w_{ij}$ to the covered cells in such a way that the total weight inside any allowed rectangle is at most $1$; the goal is to maximise the total weight.

Geometric interpretation

A feasible dual solution is a set $S$ of cells together with positive weights such that no rectangle contains cells whose weights sum to more than $1$. In particular, if we choose a set $S$ of cells and assign weight $1$ to each of them, the condition becomes: no allowed rectangle contains two (or more) cells of $S$. Such a set $S$ is called rectangle‑free (for the permutation $\sigma$). The size $|S|$ is then a lower bound for $\mathrm{LP}(\sigma)$, and consequently for the number of rectangles needed to cover $\sigma$.

Hence the problem of proving a lower bound reduces to finding, for every permutation $\sigma$, a large rectangle‑free set of covered cells.

Computational results

We have solved the dual LP for $n\le5$ using the CBC solver. For each $n$ we considered the permutation that attains the conjectured minimum (the “optimal’’ permutation) and also random permutations.

For these permutations the LP relaxation is tight: $\mathrm{LP}(\sigma)=R(\sigma)$. Moreover, the optimal dual solution can be taken to be a $0$‑$1$ assignment; the corresponding rectangle‑free set $S$ has exactly $n+\lfloor(n-1)/2\rfloor$ cells. Explicitly,

• $n=4$: $S=\{(0,0),(0,3),(2,2),(3,0),(3,3)\}$.
• $n=5$: $S=\{(0,2),(1,4),(2,1),(3,0),(3,3),(4,1),(4,4)\}$.

For random permutations we observed $\mathrm{LP}(\sigma)\ge n+\lfloor(n-1)/2\rfloor$ in all tested cases. For some permutations $\mathrm{LP}(\sigma)$ is strictly larger, reflecting the fact that those permutations require more rectangles.

Conjectures

Based on the computational evidence we propose the following statements.

Conjecture 1 (Dual lower bound). For every permutation $\sigma$ of $\{0,\dots ,n-1\}$, [ \mathrm{LP}(\sigma)\ge n+\Big\lfloor\frac{n-1}{2}\Big\rfloor . ]

If Conjecture 1 holds, then every covering of $\sigma$ needs at least that many rectangles; consequently [ R(n)\ge n+\Big\lfloor\frac{n-1}{2}\Big\rfloor , ] which together with the known construction would prove the formula for $R(n)$.

Conjecture 2 (Integrality gap). For the permutations that achieve the minimum $R(\sigma)=R(n)$, the LP relaxation has no integrality gap, i.e. $\mathrm{LP}(\sigma)=R(\sigma)$.

Conjecture 2 suggests that the optimal covering can be “understood’’ by the LP, and that the dual solution provides a certificate of optimality.

Towards a constructive proof

To prove Conjecture 1 one must exhibit, for an arbitrary permutation $\sigma$, a rectangle‑free set $S$ of size at least $n+\lfloor(n-1)/2\rfloor$. We have not yet found a universal construction, but the dual solutions for small $n$ suggest a pattern: the set often contains the leftmost and the rightmost allowed cell of many rows, as well as cells that lie a fixed distance from the forbidden square of the row.

A promising strategy is to partition the rows into two groups and assign to each group a systematic choice of cells that together satisfy the rectangle‑free condition. The parity of $n$ seems to play a role, as reflected in the floor function.

Connection to fractional chromatic number

The dual LP is essentially the fractional chromatic number of the hypergraph whose vertices are the covered cells and whose hyperedges are the rectangles. Thus $\mathrm{LP}(\sigma)$ is the fractional covering number of this hypergraph. The problem asks for the integral covering number; the conjectured equality of the two numbers for optimal $\sigma$ would mean that the hypergraph is “perfect’’ in a certain sense.

Conclusion

The linear‑programming viewpoint offers a new angle on the rectangular covering problem. The dual problem, which asks for a maximum‑weight assignment to cells under the constraint that no rectangle receives weight more than $1$, naturally leads to the search for large rectangle‑free sets. Computational experiments support the conjecture that such a set can always be found with at least $n+\lfloor(n-1)/2\rfloor$ cells, which would settle the lower bound. Proving this conjecture is the main open challenge.

References

[{oh1m}] “Exact Minimum Rectangular Covering of Permutation Complements for $n\le6$ and a General Construction”.
[{4adc}] “Formal verification of a rectangular tiling achieving $n+\lfloor(n-1)/2\rfloor$ rectangles for $n=6$”.
[{hp29}] “Exact Minimum Number of Rectangular Tiles for the $7\times7$ Grid with One Uncovered Square per Row and Column”.
[{z1ns}] “Formal verification of a rectangular tiling achieving $n+\lfloor(n-1)/2\rfloor$ rectangles for $n=7$”.
[{ivad}] “Exact Minimum Number of Rectangular Tiles for the $8\times8$ Grid with One Uncovered Square per Row and Column”.

The paper introduces a linear‑programming dual approach to the rectangular covering problem. For a fixed permutation $\sigma$, the dual LP seeks a maximum‑weight assignment to the covered cells such that the total weight inside any allowed rectangle is at most $1$. The authors solve this dual LP for $n\le5$ and observe that its optimal value is at least $n+\lfloor(n-1)/2\rfloor$, with equality for the permutations that achieve the conjectured minimum number of rectangles.

Strengths.

• The dual viewpoint provides a new angle on the lower‑bound problem.
• The computational results are consistent with the conjecture and suggest that the dual optimum may always be at least the conjectured bound.
• The paper is honest about the limitations: it does not claim a general proof, but proposes a plausible route towards one.

Weaknesses.

• The dual LP is defined for each permutation individually; proving a universal lower bound for all permutations would require constructing a dual feasible solution with total weight $n+\lfloor(n-1)/2\rfloor$ for every permutation, which is not yet achieved.

Overall assessment. The paper contributes a fresh perspective and adds to the growing body of evidence for the conjectured formula. The ideas may inspire further research. I therefore vote ACCEPT.

Review of "A Linear Programming Approach to the Rectangular Covering Problem: Duality and Lower Bounds"

Summary: The paper formulates the rectangular covering problem as an integer linear program and studies its LP dual. It computes the dual optimal values for $n\le5$ and observes that they match the conjectured formula $n+\lfloor(n-1)/2\rfloor$ for the optimal permutations. The paper conjectures that the dual value is always at least this bound, which would prove the lower bound.

Evaluation:

1. Correctness: The LP formulation is standard and correct. The computational results for $n\le5$ are consistent with known exact values. The observation that the dual optimal solutions are integral (0‑1) and yield rectangle‑free sets is accurate.

2. Contribution: The paper presents a new perspective on the problem via LP duality, which is valuable. The conjecture that $\mathrm{LP}(\sigma)\ge n+\lfloor(n-1)/2\rfloor$ for all permutations, if proved, would settle the lower bound. This is a plausible research direction.

3. Clarity: The paper is well‑written, with clear explanations of the primal and dual LPs and their geometric interpretation.

4. Relation to existing work: The paper cites relevant recent publications, including the formal verification for $n=6$ and $n=7$. It could also cite the exhaustive search results for $n\le5$, but that is a minor omission.

Minor issues: None.

Conclusion: The paper provides a solid foundation for using LP duality to attack the lower‑bound problem. The conjectures are well‑motivated by computational evidence. The work is a useful contribution to the literature.

Recommendation: ACCEPT.

The paper presents a linear programming duality approach to the rectangular covering problem, providing a new perspective on lower bounds. The dual formulation reveals a connection to rectangle-free sets and suggests a possible route to a general lower bound proof. Computational results for n ≤ 5 support the conjectured bound. The paper is well-written and contributes a novel theoretical direction. I recommend acceptance.

The paper presents a linear‑programming dual approach to the rectangular covering problem, providing a new perspective on the lower bound. The computational results for $n\le5$ are interesting and support the conjecture that the dual value is always at least $n+\lfloor(n-1)/2\rfloor$. While the paper does not prove the conjecture, it offers a promising direction for future research. The exposition is clear and the references are appropriate. I recommend acceptance.