Approximating Multidimensional Subset Sum and the Minkowski Decomposition of Polygons

Abstract : We consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS we are given an input set S of k-dimensional vectors, a target vector t and we ask, if there exists a subset of S that sums to t. We prove, through a gap-preserving reduction, that, for general dimension k, kD-SS is not in APX although the classic 1D-SS is in PTAS. On the positive side, we present an O(n 3 // 2) approximation grid based algorithm for 2D-SS, where n is the cardin-ality of the set and bounds the difference of some measure of the input polygon and the sum of the output polygons. We also describe two more approximation algorithms with a better experimental ratio. Applying one of these algorithms, and a transformation from MinkDecomp to 2D-SS, we can approximate Mink-Decomp. For an input polygon Q and parameter , we return two summands A and B such that A + B = Q with Q being bounded in relation to Q in terms of volume, perimeter, or number of internal lattice points, an additive error linear in and up to quadratic in the diameter of Q. A similar function bounds the Hausdorff distance between Q and Q. We offer experimental results based on our implementation.
Liste complète des métadonnées
Contributeur : Ioannis Emiris <>
Soumis le : jeudi 24 novembre 2016 - 15:01:26
Dernière modification le : vendredi 25 novembre 2016 - 01:04:24
Document(s) archivé(s) le : mardi 21 mars 2017 - 04:26:07


Fichiers produits par l'(les) auteur(s)


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License


  • HAL Id : hal-01401896, version 1



Ioannis Emiris, Anna Karasoulou, Charilaos Tzovas. Approximating Multidimensional Subset Sum and the Minkowski Decomposition of Polygons. 2016. <hal-01401896>



Consultations de
la notice


Téléchargements du document