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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
2 / 25
Some Denitions
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
3 / 25
Some Denitions
A horizontal (vertical) line is said to stab a rectangle r if it goes through its interior.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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 .
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
3 / 25
Approximation Algorithm for 2-Dimensional Rectangle Stabbing
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
4 / 25
Integer Programming Setting
Some Notations
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
5 / 25
Integer Programming Setting
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}.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
5 / 25
Integer Programming Setting
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}.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
5 / 25
Integer Programming Setting
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 .
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
6 / 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. 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}.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
6 / 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. 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}.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
6 / 25
Integer Programming Formulation
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
7 / 25
Integer Programming Formulation
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
7 / 25
Integer Programming Formulation
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
8 / 25
Analysis
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
Let RH (RV ) be the set of all k for which ( jVk yj 1 ) 2
iHk
xi
1 2
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
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 .
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
9 / 25
Analysis
IP formulation PH
min
iHk iH
xi
xi 1, k RH
iH
xi h
xi {0, 1}, i H
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
11 / 25
Analysis
Lemma
PH = P H and PV = P V
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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).
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
13 / 25
Analysis
Lemma
PH + PV 2P
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
Apurba Das (ISI, Kolkata) Rectangle Stabbing Problem 14 / 25
2-factor Approximation Algorithm
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
15 / 25
2-factor Approximation Algorithm
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
15 / 25
2-factor Approximation Algorithm
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
Apurba Das (ISI, Kolkata) Rectangle Stabbing Problem 15 / 25
Fixed Parameter Algorithm for 2-Dimensional Rectangle Stabbing
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
18 / 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
Instance of Parameterized Problem
A pair (I , k), where k is called the parameter
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
18 / 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
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
19 / 25
Instance of 2-Dimensional Rectangle Stabbing
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
20 / 25
Instance of 2-Dimensional Rectangle Stabbing
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
20 / 25
Instance of 2-Dimensional Rectangle Stabbing
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
21 / 25
Instance of 2-Dimensional Rectangle Stabbing
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 .
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
22 / 25
Instance of 2-Dimensional Rectangle Stabbing
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
23 / 25
Algorithm
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
24 / 25
Algorithm
Assumption
The height of every rectangle in R is bounded by a number b.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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.
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
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) ).
Apurba Das (ISI, Kolkata)
Rectangle Stabbing Problem
25 / 25
