<p>In the proof of theorem 2 in <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.6236" rel="nofollow">Improved Approximation Algorithms for Rectangle Tiling and Packing</a> by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element. </p>

<p>This implies a upper bound of $\frac{11}{5j}$ for your problem.</p>

CC BY-SA 3.0
2013-12-06T12:03:06.470Z
Thank you very much. I update the problem definition to explain which algorithm I am using.
Long Vehicle
CC BY-SA 3.0
2013-12-06T12:16:08.260Z
This bound holds independent from the algorithm.
Chao Xu
CC BY-SA 3.0
2013-12-06T12:30:43.227Z
Thanks. But this does not seem obvious to me. Can you please elaborate more?
Long Vehicle
CC BY-SA 3.0
2013-12-06T12:43:16.910Z
Every solution in this partition problem(P) is a solution to your partition(YP) problem. A solution of P is an upper bound for the optimal solution of YP. Note both P and YP have a lower bound of 1/j, and the proof of the theorem shows there exist a solution where each rectangle has weight at most $\frac{11}{5j}$ for P. Thus there exist a optimal solution where all rectangles have weight at most $\frac{11}{5j}$ for YP.
Chao Xu
CC BY-SA 3.0
2013-12-16T15:48:53.497Z
I agree with you, but a solution in my partition (YP) may not belong to a solution in this partition problem (P). YP does not use slicing algorithm row-by-row. For instance, a row with weight less than `w` in P always go to a single rectangle. Whereas, in YP that is not the case. So I cannot use Theorem 3.2 to extract the upper bound on the cell weight. Or I am missing something?
Long Vehicle
CC BY-SA 3.0
2013-12-16T15:59:11.303Z
I think I got it. The thing is that YP will not choose a worse solution than P, so $\frac{11}{5*j}$ is the upper bound.
Long Vehicle
CC BY-SA 3.0
2013-12-06T10:53:54.890Z
2013-12-06T10:59:19.673Z
2013-12-06T10:59:19.673Z
Chao Xu
<p>I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that:</p>

<ul>
<li>each element has value in the range $[0, \frac 1 j]$, $j &lt;= p$, $j$ is given,</li>
<li>the sum of all elements in the matrix is 1.</li>
</ul>

<p>The matrix is partitioned into $j$ axis-parallel non-overlapping rectangles. Each matrix cell with positive value is covered by exactly one rectangle. Whereas, each matrix cell with value 0 is covered by at most one rectangle. For each region, we sum the values inside it and obtain $region\_sum_i$, $i = 1..j$. We are given an optimal partitioning algorithm whose objective is to minimize the maximum $region\_sum_i$. The algorithm is <em>Recursive Slice-and-Dice: Binary Space Partitions</em> from <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8152" rel="nofollow">Slice and Dice : A Simple, Improved Approximate Tiling Recipe</a>. I need this algorithm due to the support for don't care regions and a general version of tiling problem. This is a DRTILE problem, but I translate this to RTILE using binary search.</p>

<p><strong>The problem</strong> is to find an upper bound on $region\_sum_i$ for the optimal solution under worst-case input with given constraints. I need this as I am doing competitive analysis.</p>

<p>I appreciate any help! Many thanks!</p>

CC BY-SA 3.0
2013-12-06T01:17:59.663Z
I'm not sure I understand the problem.  Do you mean that the partition into rectangles is given?  (If so, why do we need an upper bound -- we can just compute subset_sum directly, right?)  Or do you mean that the partition is not given and the goal is to find a partition with the specified constraints and minimizing the maximum subset_sum?  Is $j$ given?  What does it mean to say you already have an algorithm for partitioning?  If your algorithm computes the optimal partition, doesn't that immediately give you a tight upper bound?
D.W.
CC BY-SA 3.0
2013-12-06T01:58:40.177Z
I think he meant the upper bound for the optimal solution.
Chao Xu
CC BY-SA 3.0
2013-12-06T08:11:54.837Z
I think it be nicer if you replace $m$ with $1$, as scaling doesn't matter. Do you want an upper bound in case of the $OPT$ or in case of $j$?
Chao Xu
CC BY-SA 3.0
2013-12-06T08:18:53.950Z
@Chao Xu Thank you very much for your comments. I clarified the problem definition.
I am not sure I understand your last question. I want an upper bound in case of OPT with given $j$.
Long Vehicle
<partition-problem><sparse-matrix>
Partitioning a matrix into equal-sized regions: finding the maximum
Long Vehicle
# Partitioning a matrix into equal-sized regions: finding the maximum

(Asked by: username_0 on 2013-12-05)

I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that:

* each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given,
* the sum of all elements in the matrix is 1.

The matrix is partitioned into $j$ axis-parallel non-overlapping rectangles. Each matrix cell with positive value is covered by exactly one rectangle. Whereas, each matrix cell with value 0 is covered by at most one rectangle. For each region, we sum the values inside it and obtain $region\\_sum\_i$, $i = 1..j$. We are given an optimal partitioning algorithm whose objective is to minimize the maximum $region\\_sum\_i$. The algorithm is *Recursive Slice-and-Dice: Binary Space Partitions* from [Slice and Dice : A Simple, Improved Approximate Tiling Recipe](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8152). I need this algorithm due to the support for don't care regions and a general version of tiling problem. This is a DRTILE problem, but I translate this to RTILE using binary search.

**The problem** is to find an upper bound on $region\\_sum\_i$ for the optimal solution under worst-case input with given constraints. I need this as I am doing competitive analysis.

I appreciate any help! Many thanks!

**Tags:** partition-problem, sparse-matrix

> **Comments:**
> **username_1**: I'm not sure I understand the problem.  Do you mean that the partition into rectangles is given?  (If so, why do we need an upper bound -- we can just compute subset_sum directly, right?)  Or do you mean that the partition is not given and the goal is to find a partition with the specified constraints and minimizing the maximum subset_sum?  Is $j$ given?  What does it mean to say you already have an algorithm for partitioning?  If your algorithm computes the optimal partition, doesn't that immediately give you a tight upper bound?  
> **username_2**: I think he meant the upper bound for the optimal solution.  
> **username_2**: I think it be nicer if you replace $m$ with $1$, as scaling doesn't matter. Do you want an upper bound in case of the $OPT$ or in case of $j$?  
> **username_0**: @username_2 Thank you very much for your comments. I clarified the problem definition. I am not sure I understand your last question. I want an upper bound in case of OPT with given $j$.  

---

## 1 answers

### Answer by username_2 on 2013-12-06. Score: 2

In the proof of theorem 2 in [Improved Approximation Algorithms for Rectangle Tiling and Packing](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.6236) by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element.

This implies a upper bound of $\frac{11}{5j}$ for your problem.

> **Comments:**
> **username_0**: Thank you very much. I update the problem definition to explain which algorithm I am using.  
> **username_2**: This bound holds independent from the algorithm.  
> **username_0**: Thanks. But this does not seem obvious to me. Can you please elaborate more?  
> **username_2**: Every solution in this partition problem(P) is a solution to your partition(YP) problem. A solution of P is an upper bound for the optimal solution of YP. Note both P and YP have a lower bound of 1/j, and the proof of the theorem shows there exist a solution where each rectangle has weight at most $\frac{11}{5j}$ for P. Thus there exist a optimal solution where all rectangles have weight at most $\frac{11}{5j}$ for YP.  
> **username_0**: I agree with you, but a solution in my partition (YP) may not belong to a solution in this partition problem (P). YP does not use slicing algorithm row-by-row. For instance, a row with weight less than `w` in P always go to a single rectangle. Whereas, in YP that is not the case. So I cannot use Theorem 3.2 to extract the upper bound on the cell weight. Or I am missing something?  
> **username_0**: I think I got it. The thing is that YP will not choose a worse solution than P, so $\frac{11}{5*j}$ is the upper bound.  

---

