Forskning ved Københavns Universitet - Københavns Universitet

Forside

Approximation schemes for maximum weight independent set of rectangles

Publikation: Bidrag til bog/antologi/rapportBidrag til bog/antologiForskningfagfællebedømt

Standard

Approximation schemes for maximum weight independent set of rectangles. / Adamaszek, Anna Maria; Wiese, Andreas.

2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 2013. s. 400-409.

Publikation: Bidrag til bog/antologi/rapportBidrag til bog/antologiForskningfagfællebedømt

Harvard

Adamaszek, AM & Wiese, A 2013, Approximation schemes for maximum weight independent set of rectangles. i 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, s. 400-409. https://doi.org/10.1109/FOCS.2013.50

APA

Adamaszek, A. M., & Wiese, A. (2013). Approximation schemes for maximum weight independent set of rectangles. I 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (s. 400-409). IEEE. https://doi.org/10.1109/FOCS.2013.50

Vancouver

Adamaszek AM, Wiese A. Approximation schemes for maximum weight independent set of rectangles. I 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE. 2013. s. 400-409 https://doi.org/10.1109/FOCS.2013.50

Author

Adamaszek, Anna Maria ; Wiese, Andreas. / Approximation schemes for maximum weight independent set of rectangles. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 2013. s. 400-409

Bibtex

@inbook{a018f4f1d1d64fe1b4a17d88165c8f91,
title = "Approximation schemes for maximum weight independent set of rectangles",
abstract = "In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1+epsilon)-approximation algorithm for the MWISR problem with quasi-polynomial running time 2^{poly(log n/epsilon)}. In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n / log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to Arora et al. this allows us to upper bound our approximation ratio by (1+epsilon). Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1+epsilon)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem.",
author = "Adamaszek, {Anna Maria} and Andreas Wiese",
year = "2013",
month = "10",
doi = "10.1109/FOCS.2013.50",
language = "English",
isbn = "978-0-7695-5135-7",
pages = "400--409",
booktitle = "2013 IEEE 54th Annual Symposium on Foundations of Computer Science",
publisher = "IEEE",

}

RIS

TY - CHAP

T1 - Approximation schemes for maximum weight independent set of rectangles

AU - Adamaszek, Anna Maria

AU - Wiese, Andreas

PY - 2013/10

Y1 - 2013/10

N2 - In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1+epsilon)-approximation algorithm for the MWISR problem with quasi-polynomial running time 2^{poly(log n/epsilon)}. In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n / log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to Arora et al. this allows us to upper bound our approximation ratio by (1+epsilon). Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1+epsilon)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem.

AB - In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1+epsilon)-approximation algorithm for the MWISR problem with quasi-polynomial running time 2^{poly(log n/epsilon)}. In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n / log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to Arora et al. this allows us to upper bound our approximation ratio by (1+epsilon). Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1+epsilon)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem.

U2 - 10.1109/FOCS.2013.50

DO - 10.1109/FOCS.2013.50

M3 - Book chapter

SN - 978-0-7695-5135-7

SP - 400

EP - 409

BT - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science

PB - IEEE

ER -

ID: 144250945