|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line | | José R. Correa
; Laurent Feuilloley
; José A. Soto
; | | Date: |
25 Sep 2013 | | Abstract: | Finding a maximum independent set of a given family of axis-parallel
rectangles is a basic problem in computational geometry and combinatorics. This
problem has attracted attention since the sixties, when Wegner conjectured that
the corresponding duality gap, i.e., the ratio between the maximum independent
set and the minimum hitting set, is bounded by a universal constant. In this
paper we improve upon recent results of Chepoi and Felsner and prove that when
the given family of rectangles is intersected by a diagonal, this ratio is
between 2 and 4. For the upper bound we derive a simple combinatorial argument
that first allows us to reprove results of Hixon, and Chepoi and Felsner and
then we adapt this idea to obtain the improved bound in the diagonal
intersecting case. From a computational complexity perspective, although for
general rectangle families the problem is known to be NP-hard, we derive an
$O(n^2)$ algorithm for the maximum weight independent set when, in addition to
intersecting a diagonal, the rectangles intersect below it. This improves and
extends a classic result of Lubiw. As a consequence, we obtain a
2-approximation algorithm for the maximum weight independent set of rectangles
intersecting a diagonal. | | Source: | arXiv, 1309.6659 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER