Approximation Algorithms for max-min tiling Authors



Yüklə 482 b.
tarix15.03.2018
ölçüsü482 b.
#32199


Approximation Algorithms for MAX-MIN tiling

  • Authors

  • Piotr Berman, Bhaskar DasGupta,

  • S. Muthukrishman

  • Published on

  • Journal of Algorithms, 2003

  • Presented by

  • Sera Kahruman


Outline

  • Definition

  • Approximation algorithms

    • Greedy Slice and Dice
    • Recursive slice and dice-Binary space partitionings
  • Conclusion



Outline

  • Definition

  • Approximation algorithms

    • Greedy Slice and Dice
    • Recursive slice and dice-Binary space partitionings
  • Conclusion



Definition

  • Given a 2-dimensional array A[1,…,n][1,…,n]

  • s.t. each A[i][j] stores a non-negative number

  • A tile is a subarray A[l,…,r][t,…,b] of A

  • Weight of a tile T, w(T) = sum of all array entries in that tile

  • A tiling of A is a collection of tiles of A s.t. each entry of A is contained in exactly one tile



Max-Min Tiling Problem

  • Given a weight bound W, find a tiling of A such that:

  • Each tile is of weight at least W

  • The number of tiles is maximized

  • Max-Min tiling is NP-hard!

  • Data mining…..an application area



More definitions

  • (r, s) approximation of max-min tiling is a solution that produces a tiling of A with at least rp* tiles each of which has weight at least s(W-c) where;

    • p* = max number of tiles used in an optimal solution
    • c≥0 is a constant


Slice and Dice Technique

  • Partition the input array into a number of slices (rectangles) using some criteria (depending on the problem)…..slicing step

  • Search for a better solution by looking at the neighbor slices and repartitioning the entries…..dicing step



Outline

  • Definition

  • Approximation algorithms

    • Greedy Slice and Dice
    • Recursive slice and dice-Binary space partitionings
  • Conclusion



Approximation algorithms for Max-Min tiling

  • Greedy slice and dice

    • Linear in number of non-zero entries (m)
    • Greedily slice the array into strips and dice each slice
  • Recursive slice and dice: binary space partitionings



Greedy Slice and Dice Algorithm



Greedy Slice & Dice Algorithm

  • Scale the array such that W=1 if necessary

  • After scaling w(A) becomes an upper bound

  • A good tile is a tile whose weight is at least 1

  • The algorithm finds a solution with t good tiles

  • Such that w(A)< r*t + 2



Slicing Step

  • Slices are composed of complete rows

  • Start with the bottom row and proceed upwards

  • Find minimal slices

  • Last slice is the remainder slice, others regular



Example : Slicing step



Dicing Step

  • Partition each slice Si using the slicing algorithm considering columns instead of rows

  • V-slices (vertical slices) are produced

  • α(i) = # of V-slices obtained from Si

  • Vi,1 , …. , Vi, α(i) are regular, Vi, α(i)+1 remainder

  • Combine Vi, α(i)+1 with Vi, α(i) for preliminary partition



Example: Dicing step



Dicing step : Cont’

  • Estimate weight of each part

    • w(VLi,j) < 1
    • Summation of all w(VRi,j) of Si < 1
    • w(VCi,j) ≤ 1


Cont’

  • Guarantee an approx. ratio of 4 (use at least floor(w(A))/4 tiles)

  • Proof :

  • Let t be the # of tiles obtained using the algorithm

      • w(Si) < 2+ 2α(i) ≤ 4α(i)
      • w(A) < 1 + w(S1)+……..+w(SL)
      • < 1 + 4*(α(1)+……+ α(L) )
      • < 1 + 4*t
      • 4*t ≥ floor(w(A))
  • Do additional dicing to improve the ratio



Additional Dicing Step



Cont’

  • With the additional dicing step, approximation ratio becomes 3.

  • Proof: need to show that t ≥ floor((w(A)+1)/3)

  • w(A) < 3*t + 2

  • w(S1)+……..+w(SL) < 3*t + 1



Outline

  • Definition

  • Approximation algorithms

    • Greedy Slice and Dice
    • Recursive slice and dice-Binary space partitionings
  • Conclusion



Recursive Slice & Dice

  • Based on binary space partitioning of a set of isothetic rectangles

  • isothetic rectangle = rectangle with edges parallel to principal axes

  • Given a rectangular region R containing a set of n disjoint isothetic rectangles, a BSP of R consists of recursively partitioning R by a horizontal or vertical line into 2 sub regions and continuing in this manner for all the sub regions until each obtained region has at most 1 rectangle. If a rectangle is cut by a line, it is split into disjoint rectangles

  • Size(BSP)= # of regions produced

  • A set of rectangles form a tiling if they partition some rectangular region R.

  • Use dynamic programming – min size BSP in O(n5) time.



Theorems



Recursive Slice & Dice

  • How to compute such a BSP of A?

  • Definitions

    • HBP : Hierarchical binary partition
    • An HBP of an array is either the entire array or the unions of HBPs of the two sub arrays of the array.
    • Γ(I,j,k,l,p) = HBP of the sub array A[ i,.,j ][ k,…,l ] in which there exists p tiles of weight at least s*W.
  • A BSP of OPT is also a HBP of A

  • Use dynamic programming to find

  • {Γ(1,n,1,n,p) | 0 ≤ p ≤ n2 }



Time analysis

  • There are at most O(n4) sub arrays of A

  • If the weight of the sub array A[ i,.,j ][ k,..,l ] is at least s*W, then

    • # of ways to construct a HBP of it is
    • (j - i) + (l – k ) + 3 ≤ 2n-1…………O( n )
  • 0 ≤ p ≤ n2

  • Since we are looking for the answer for each p,

  • Total running time is O(n4 * n * n2)=O(n7 )



Outline

  • Definition

  • Approximation algorithms

    • Greedy Slice and Dice
    • Recursive slice and dice-Binary space partitionings
  • Conclusion



Conclusion

  • Authors introduce two approximation algorithms for MAX-MIN tiling problem using slice and dice technique

  • They state that efficient approximation algorithms for this problem in higher dimensions can be improved using variations of this approach



QUESTIONS ???



Homework

  • Formulate MAX-MIN tiling problem as an optimization problem.

  • In the paper, authors also mention MIN-MAX tiling problem. Define MIN-MAX tiling problem and state the main differences between the two problems.



Yüklə 482 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə