Rectangle Stabbing

Constant Ratio Approximation Algorithm and Parameterized Algorithm and Complexity
Apurba Das
M.Tech (CS), 2009-2011 Indian Statistical Institute, Kolkata
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
1 / 25
The Problem
Given a set R of n rectangles, which are aligned to the x and y axes in the two-dimensional space, whose corners are all located at integer points and whose areas are more than 1. Using at least h horizontal lines and v vertical lines, respectively, the problem is to stab all the rectangles by the minimum number of lines located at integer coordinates.
2 / 25
The Problem
Given a set R of n rectangles, which are aligned to the x and y axes in the two-dimensional space, whose corners are all located at integer points and whose areas are more than 1. Using at least h horizontal lines and v vertical lines, respectively, the problem is to stab all the rectangles by the minimum number of lines located at integer coordinates.
Hardness of the Problem

The Rectangle stabbing problem in 2-Dimension is NP-hard Optimization problem.
2 / 25
Some Denitions
3 / 25
Some Denitions
A horizontal (vertical) line is said to stab a rectangle r if it goes through its interior.
3 / 25
Some Denitions
A horizontal (vertical) line is said to stab a rectangle r if it goes through its interior. All corners of r are integer points. A horizontal line y = ch stabs r if ah + 1 ch bh 1 holds for the coordinate y = ah (y = bh ) of the lower edge (upper edge) of r . A vertical line x = cv stabs r if av + 1 cv bv 1 holds for the coordinate x = av (x = bv ) of the left edge (right edge) of r .
3 / 25
Approximation Algorithm for 2-Dimensional Rectangle Stabbing
4 / 25
Integer Programming Setting
Some Notations
5 / 25
Some Notations H : Set of all horizontal lines H = {y = ah + 1, y = bh 1 | y = ah is the lower edge and y = bh is the upper edge of a rectangle r R such that bh ah 2}.
5 / 25
Some Notations H : Set of all horizontal lines H = {y = ah + 1, y = bh 1 | y = ah is the lower edge and y = bh is the upper edge of a rectangle r R such that bh ah 2}. V : Set of all vertical lines V = {x = av + 1, x = bv 1 | x = av is the left edge and x = bv is the right edge of a rectangle r R such that bv av 2}.
5 / 25
Some Notations H : Set of all horizontal lines H = {y = ah + 1, y = bh 1 | y = ah is the lower edge and y = bh is the upper edge of a rectangle r R such that bh ah 2}. V : Set of all vertical lines V = {x = av + 1, x = bv 1 | x = av is the left edge and x = bv is the right edge of a rectangle r R such that bv av 2}. All lines for stabbing are to be taken from H V .
5 / 25
Integer Programming Setting (Contd...)
xi : Decision variable corresponding to the ith horizontal line in the set H. yj : Decision variable corresponding to the jth vertical line in the set V.
6 / 25
xi : Decision variable corresponding to the ith horizontal line in the set H. yj : Decision variable corresponding to the jth vertical line in the set V. Hk : Set of horizontal lines in H that stab rectangle rk , k {1, 2, ..., n}. Vk : Set of vertical lines in V that stab rectangle rk , k {1, 2, ..., n}.
6 / 25
xi : Decision variable corresponding to the ith horizontal line in the set H. yj : Decision variable corresponding to the jth vertical line in the set V. Hk : Set of horizontal lines in H that stab rectangle rk , k {1, 2, ..., n}. Vk : Set of vertical lines in V that stab rectangle rk , k {1, 2, ..., n}. [n] : The set {1, 2, ..., n}.
6 / 25
Integer Programming Formulation
7 / 25
Integer Programming Problem P

min
iHk iH
xi +
jV
yj
xi +
jVk iH jV
yj 1, k [n]
xi h yj v
xi , yi {0, 1}, i H, j V
7 / 25
Relaxation of Integer Programming Problem P

min
iHk iH
xi +
jV
yj
xi +
jVk iH jV
yj 1, k [n]
xi h yj v
xi , yi 0, i H, j V
8 / 25
Analysis
9 / 25
Analysis
Let (xi , i H; yj , j V ) be an optimal fractional solution to P It satises either k [n]

iHk
xi
1 2
or
jVk
yj
1 2
for every rectangle
9 / 25
Analysis

iHk
xi
1 2
or
jVk
yj
1 2
for every rectangle
Let RH (RV ) be the set of all k for which ( jVk yj 1 ) 2
iHk
xi
1 2
9 / 25
Analysis

iHk
xi
1 2
or
jVk
yj
1 2
for every rectangle
Let RH (RV ) be the set of all k for which ( jVk yj 1 ) 2
iHk
xi
1 2
Based on the above denitons dene two IP PH and PV .
9 / 25
Analysis
IP formulation PH
min
iHk iH
xi
xi 1, k RH
iH
xi h
xi {0, 1}, i H
10 / 25
Analysis
IP formulation PH
min
iHk iH
xi
xi 1, k RH
iH
xi h
xi {0, 1}, i H
IP formulation PV
min
jVk jV
yj
yj 1, k RV
jV
yj v
yj {0, 1}, j V
Apurba Das (ISI, Kolkata) Rectangle Stabbing Problem 10 / 25
Analysis
Every constraint in integer programs PH and PV contains a subset of variables in the corresponding constraint of P. Let a feasible solution of PH is xH and a feasible solution of PV is yV . The composite solution (xH , yV ) is feasible in P
11 / 25
Analysis
Every constraint in integer programs PH and PV contains a subset of variables in the corresponding constraint of P. Let a feasible solution of PH is xH and a feasible solution of PV is yV . The composite solution (xH , yV ) is feasible in P Let linear programming relaxation of PH is P H and of PV is P V
P , P , PH , PV , P H , P V are the optimal values of the programs P, P, PH , PV , P H , P V respectively.
11 / 25
Analysis
Lemma
PH = P H and PV = P V
12 / 25
Analysis
Lemma
PH = P H and PV = P V
Proof Idea:
First consider PH Order all the horizontal lines i H from the lowest to the highest All the horizontal lines in Hk of each k are consecutive in this ordering. The rows of the coecient matrix have the interval properties (elements 1s are located consecutively in each row).
12 / 25
Analysis
Proof Idea(Contd...):
Therefore the matrix is totally unimodular Any fractional optimal solution of an LP of which the coecient matrix is totally unimodular gives the integral solutions only.
This proves PH = P H Similarly it can be proved that PV = P V
13 / 25
Analysis
Lemma
PH + PV 2P
14 / 25
Analysis
Lemma
PH + PV 2P
Proof Idea:
Let (x, y ) be an optimal fractional solution to problem P. For every constraint of PH for k RH , iHk 2xi 1
iH iHk
xi
1 2
implies 2x i h
2xi >
iH
xi and
iH
x i h implies
iH
2x is a feasible solution to P H In the similar way 2y is a feasible solution to P V it follows that P H + P V 2P

From the previous lemma and from the fact that P P the lemma is proved
2-factor Approximation Algorithm
15 / 25

Input & Output
Input A set R of n rectangles aligned to the x and y axes, and nonnegetive integers h and v . Output h ( h) horizontal lines and v ( v ) vertical lines that together stab all rectangles in R
15 / 25

Input & Output
Input A set R of n rectangles aligned to the x and y axes, and nonnegetive integers h and v . Output h ( h) horizontal lines and v ( v ) vertical lines that together stab all rectangles in R
The Algorithm
Step 1. Solve linear program P, and obtain the fractional optimal solution (x, y ) = (xi , i H; yj , j V ). Step 2. Construct the two integer programs PH and PV from (x, y ), and obtain their optimal solutions xH and yV (by solving linear programs P H and P V ), respectively.
Step 3. Output the ith horizontal lines such that (xH )i = 1 and the ) = 1 jth vertical lines such that (yV j
Fixed Parameter Algorithm for 2-Dimensional Rectangle Stabbing
16 / 25
Problem Denition
Given a set of axis parallel rectangles R, the rectangles have to be stabbed with at most k lines chosen from a gives set L of veretical and horizontal lines.
17 / 25
Preliminaries
Parameterized Problem
A parameterized problem is a subset of N where alphabet and N is the set of natural numbers. is a nite
18 / 25
Preliminaries
Instance of Parameterized Problem

A pair (I , k), where k is called the parameter
18 / 25
Preliminaries
Instance of Parameterized Problem

A pair (I , k), where k is called the parameter
Running time
The running time of an algorithm is viewed as a function of two quantities: The size of the problem instance The parameter
18 / 25
Preliminaries
Fixed Parameter Tractable(FPT)
A parameterized problem is said to be xed parameter tractable (FPT) with respect to the parameter k if there exists an algorithm for the problem running in f (k) | I |O(1) time, where f is a computable function only depending on k.
19 / 25
Preliminaries
Fixed Parameter Tractable(FPT)
A parameterized problem is said to be xed parameter tractable (FPT) with respect to the parameter k if there exists an algorithm for the problem running in f (k) | I |O(1) time, where f is a computable function only depending on k.
Data Reduction
A data reduction rule is a polynomial time algorithm which takes as input a problem instance (I , k) and outputs an instance (I , k ) such that | I || I | and k k, and (I , k ) is a YES-instance i (I , k) is a YES-instance. (I , k ) is called problem karnel. If a parameterized problem has a kernel, then it is FPT
19 / 25
Instance of 2-Dimensional Rectangle Stabbing
20 / 25
Instance
Let (R,L,k) is an instance. R is the set of axis parallel rectangles. L = V H. V = {v1 , v2 , . . . , vn } are the vertical lines ordered from left to right. H = {h1 , h2 , . . . , hm } are the horizontal lines ordered from top to bottom.
20 / 25
Denitions
lx(r) : index of the leftmost line intersecting r R rx(r) : index of the rightmost line intersecting r R tx(r) : index of the topmost line intersecting r R bx(r) : index of the bottommost line intersecting r R wh(r) = rx(r) - lx(r) + 1 is the nnumber of vertical lines intersecting r. ht(r) = bx(r) - tx(r) + 1 is the number of horizontal lines intersecting r.
21 / 25
Data Reduction Rules

If there is a rectangle that is intersected by no line from L, then the given instance is a NO-instance. If there is a rectangle that is intersected by exactly one line l L, then delete all rectangles that are intersected by l, delete l, and decrease k by 1. If there are two lines l1 , l2 L such that every rectangle in R that is intersected by l2 is also intersected by l1 , then delete l2 . If there are two rectangles r1 , r2 R such that every line in L that intersects r1 also intersects r2 , then delete r2 .
22 / 25
Observations
In a reduced problem instance, for every vertical line vj V there exists rectangles r , r R with lx(r) = j and rx(r) = j. In a reduced problem instance, for every horizontal line hi H there exists rectangles r , r R with tx(r) = i and bx(r) = i. In the reduced problem instance, there exists rectangles r , r R such that wh(r) = 1 and ht(r) = 1.
23 / 25
Algorithm
24 / 25
Algorithm
Assumption
The height of every rectangle in R is bounded by a number b.
24 / 25
Algorithm
Assumption
The height of every rectangle in R is bounded by a number b.
Simple Search Tree Algorithm

At every step, apply the data reduction rules until the current instance is reduced. Search for a rectangle r R with rx(r ) = 1, and branch. either select the single vertical line that intrsects r or select one of the at most b horizontal lines that intersect r.
24 / 25
Algorithm
Copmplexity
In the search tree, starting from a rectangle at root (b+1) branching possibilities are there. The height of the tree can be no more than k. So, for each rectangle search tree exploration would required (b + 1)k time. Therefore, total running time of this algorithm is O((b + 1)k nO(1) ).
25 / 25

Rectangle Stabbing

Uploaded by

Copyright:

Available Formats

Rectangle Stabbing

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Rectangle Stabbing

Uploaded by

Copyright:

Available Formats

Constant Ratio Approximation Algorithm and Parameterized Algorithm and Complexity

Apurba Das (ISI, Kolkata)