Authors Piotr Berman, Bhaskar DasGupta, S. Muthukrishman Published on Journal of Algorithms, 2003 Presented by Sera Kahruman
Outline Definition - 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: 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
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 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’ 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 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.
Dostları ilə paylaş: |