## Abstract

For the case of large axis-parallel rectangles, we provide a polynomial time (1 + ε)-approximation for the maximum weight independent set. Specifically, we consider the problem where each rectangle has one edge whose length is at least a constant fraction of the length of the corresponding edge of the bounding box of all the input elements. This is now the most general case for which a PTAS is known, and it requires a new and involved partitioning scheme, which should be of independent interest.

Original language | English |
---|---|

Article number | 29 |

Pages (from-to) | 1-40 |

Number of pages | 40 |

Journal | Journal of the ACM |

Volume | 66 |

Issue number | 4 |

Early online date | 19 Jun 2019 |

DOIs | |

Publication status | Published - Aug 2019 |

### Funding

Anna Adamaszek supported by the Danish Council for Independent Research DFF-MOBILEX mobility grant. Work on this article Sariel Har-Peled was partially supported by a NSF AF award CCF-1217462. Authors’ addresses: A. Adamaszek, Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, Denmark; email: [email protected]; S. Har-Peled, 201 N. Goodwin Avenue, Urbana, IL 61801-2302, USA; email: [email protected]; A. Wiese (corresponding author), Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Beauchef 851 Of. 705 Piso 7, Santiago Centro, Chile; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. 0004-5411/2019/06-ART29 $15.00 https://doi.org/10.1145/3326122 Anna Adamaszek supported by the Danish Council for Independent Research DFF-MOBILEX mobility grant. Work on this article Sariel Har-Peled was partially supported by a NSF AF award CCF-1217462.

Funders | Funder number |
---|---|

Danish Council for Independent Research DFF-MOBILEX | |

National Science Foundation | CCF-1217462 |

Directorate for Computer and Information Science and Engineering | 1217462 |

Natur og Univers, Det Frie Forskningsråd |