Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have been struggling with a research problem. The problem can be formalized as follows:

Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ rectangles, such that each non-zero cell is covered once (non overlapping cover), and zero cell may or may not be covered by a rectangle. Given that weight of a rectangle is $a \cdot\text{perimeter}$ + $b\cdot \text{sum_of_cell_values_inside}$, design an algorithm which minimizes the maximum weight of a rectangle.

Ideally we are seeking for an approximation algorithm with at most a poly-logarithmic cost in terms of n or m. That said, ideally, we would like an approximation algorithm with competitive ratio=$2$ and $O(n\log n+m\log m)$ time complexity.

I hope anyone can give us some leads for solving this problem

Comments:

  • It is allowed that either a or b is equal to 0, but not both of them. Setting one of these constants to zero simplifies the problem, so we are actually interested in the general case, 0 < a, b <= 1. Partition means that all the positive cells are covered exactly once, and zero cells are covered at most once.

  • J<< n and a and b are just weights whose values range between 0 and 1. That is 0<= a,b <=1

  • The matrix is sparse, that is the number of non-zero elements in the matrix is O(nlogn + mlogm)

share|improve this question
    
Presumably $J$ is small? Otherwise the solution would be to enclose each cell in its own square... –  Joseph O'Rourke Sep 10 '13 at 15:27
    
And presumably $a > 0$, otherwise all covers have equal weight. –  Joseph O'Rourke Sep 10 '13 at 23:45
    
yes J is small. That is J<< n and a and b are just weights whose values range between 0 and 1. That is 0<= a,b <=1 –  SaSa Sep 11 '13 at 13:47
1  
@SaSa: what do you mean by partition? imo in a partition every cell is covered exactly once. do you want every cell covered at most once (and at least once if it's positive)? also, do you know the answer for a=0 or b=0? –  domotorp Sep 13 '13 at 15:25
1  
I am Sasa's collaborator, and I'll try to clarify the problem statement. @domotorp: It is allowed that either a or b is equal to 0, but not both of them. Setting one of these constants to zero simplifies the problem, so we are actually interested in the general case, 0 < a, b <= 1. Partition means that all the positive cells are covered exactly once, and zero cells are covered at most once. –  Long Vehicle Sep 17 '13 at 7:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.