Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

Sayan Bandyapadhyay; Santanu Bhowmick; Kasturi Varadarajan

doi:10.1137/1.9781611973730.96

Back

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

Conference proceeding

Open access

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

Sayan Bandyapadhyay, Santanu Bhowmick and Kasturi Varadarajan

Society for Industrial and Applied Mathematics and Association for Computing Machinery. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp.1457-1470

01/01/2015

DOI: 10.1137/1.9781611973730.96

Files and links (1)

url

https://doi.org/10.1137/1.9781611973730.96View

Published (Version of record) Open Access

Abstract

Recently, Adamaszek and Wiese presented a quasi-polynomial time approximation scheme (QPTAS) for the problem of computing a maximum weight independent set for certain families of planar objects. This major advance on the problem was based on their proof that a certain type of separator exists for any independent set. Subsequently, Har-Peled simplified and generalized their result. Mustafa et al. also described a simplification, and somewhat surprisingly, showed that QPTAS's can be obtained for certain, albeit special, type of covering problems. Building on these developments, the authors revisit two NP-hard geometric partitioning problems. Partitioning problems combine the features of packing and covering. In particular, since the optimal solution does form a packing, the separator theorems are potentially applicable. Nevertheless, the two partitioning problems we study bring up additional difficulties that are worth examining in the context of the wider applicability of the separator methodology. They show how these issues can be handled in presenting quasi-polynomial time algorithms for these two problems with improved approximation guarantees.

Algorithms

Mathematical Models

Approximation

Construction

Covering

Mathematical analysis

Partitioning

Separators

Details

Title: Subtitle: Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation
Creators: Sayan Bandyapadhyay
Santanu Bhowmick
Kasturi Varadarajan
Resource Type: Conference proceeding
Publication Details: Society for Industrial and Applied Mathematics and Association for Computing Machinery. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp.1457-1470
DOI: 10.1137/1.9781611973730.96
Language: English
Date published: 01/01/2015
Academic Unit: Computer Science
Record Identifier: 9984259417002771

Metrics

33 Record Views