Erlebach Paper (SODA 2008)
Erlebach paper (SODA 2008)
Unique Coverage Problem
- NP-hard for unit-disk model - proven by reduction from Independent Set
- extended to budgeted low-covering problem
- For bounded ply, FPTAS
- approx. algo works by looking at squares of size $\delta * \delta$. If a $\frac{1}{c}$ algo exists for these there exists a $\frac{\delta^2}{(1+\delta)^2}$ approximation algorithm. In particular there exists 1/2-approx algo for a square of size 1/2*1/2 Hence a 1/18-approx algo for general case. - Use of envelopes of disks and triples for this proof
Minimum Membership Set Cover Problem
- NP-hard
- not PTAA with ratio better than 2
- for Unit Square, 5-approx if optimum objective value bounded by constant
- Algo: (for unit SQUARES, NOT unit DISKS) use of horizontal slabs, envelopes, sweep-lines, bound on maximum membership
- - 2 approx for any slab
- - proper admissible tuples of squares per sweep line (point)
- - 5 approx in general
What is rectilinear embedding ?
Unique Coverage Problem
- NP-hard for unit-disk model - proven by reduction from Independent Set
- extended to budgeted low-covering problem
- For bounded ply, FPTAS
- approx. algo works by looking at squares of size $\delta * \delta$. If a $\frac{1}{c}$ algo exists for these there exists a $\frac{\delta^2}{(1+\delta)^2}$ approximation algorithm. In particular there exists 1/2-approx algo for a square of size 1/2*1/2 Hence a 1/18-approx algo for general case. - Use of envelopes of disks and triples for this proof
Minimum Membership Set Cover Problem
- NP-hard
- not PTAA with ratio better than 2
- for Unit Square, 5-approx if optimum objective value bounded by constant
- Algo: (for unit SQUARES, NOT unit DISKS) use of horizontal slabs, envelopes, sweep-lines, bound on maximum membership
- - 2 approx for any slab
- - proper admissible tuples of squares per sweep line (point)
- - 5 approx in general
What is rectilinear embedding ?
posted by Gaurav at 1:14 PM
0 Comments:
Post a Comment
<< Home