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 / e^2) approximation grid based algorithm for 2D-SS, where n is the cardinality of the set and e>0 bounds the difference of some measure of the input polygon and the sum of the output polygons. We also describe two 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 e, 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.
Type de document :
Article dans une revue
Mathematics for Computer Science, Birkhauser, 2017, 11, pp.35-48. 〈10.1007/s11786-017-0297-1〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01401896
Contributeur : Ioannis Emiris <>
Soumis le : jeudi 24 novembre 2016 - 15:01:26
Dernière modification le : vendredi 17 novembre 2017 - 01:11:27
Document(s) archivé(s) le : mardi 21 mars 2017 - 04:26:07

Fichiers

ApprMinkDecomp_mcs_EKT.pdf
Fichiers produits par l'(les) auteur(s)

Licence


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

Identifiants

Collections

Citation

Ioannis Emiris, Anna Karasoulou, Charilaos Tzovas. Approximating Multidimensional Subset Sum and the Minkowski Decomposition of Polygons. Mathematics for Computer Science, Birkhauser, 2017, 11, pp.35-48. 〈10.1007/s11786-017-0297-1〉. 〈hal-01401896〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

83