2
$\begingroup$

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. 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!

Improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Dec 6 '13 at 1:17
  • $\begingroup$ I think he meant the upper bound for the optimal solution. $\endgroup$ – Chao Xu Dec 6 '13 at 1:58
  • $\begingroup$ 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$? $\endgroup$ – Chao Xu Dec 6 '13 at 8:11
  • $\begingroup$ @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$. $\endgroup$ – Long Vehicle Dec 6 '13 at 8:18
2
$\begingroup$

In the proof of theorem 2 in Improved Approximation Algorithms for Rectangle Tiling and Packing 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.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you very much. I update the problem definition to explain which algorithm I am using. $\endgroup$ – Long Vehicle Dec 6 '13 at 12:03
  • $\begingroup$ This bound holds independent from the algorithm. $\endgroup$ – Chao Xu Dec 6 '13 at 12:16
  • $\begingroup$ Thanks. But this does not seem obvious to me. Can you please elaborate more? $\endgroup$ – Long Vehicle Dec 6 '13 at 12:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Chao Xu Dec 6 '13 at 12:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Long Vehicle Dec 16 '13 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.