Approximating Multidimensional Subset Sum and the Minkowski Decomposition of Polygons

Ioannis Emiris 1, 2 Anna Karasoulou 2 Charilaos Tzovas 2
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , National and Kapodistrian University of Athens
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.
Liste complète des métadonnées

https://hal.inria.fr/hal-01401896
Contributor : Ioannis Emiris <>
Submitted on : Thursday, November 24, 2016 - 3:01:26 PM
Last modification on : Wednesday, October 17, 2018 - 5:02:07 PM
Document(s) archivé(s) le : Tuesday, March 21, 2017 - 4:26:07 AM

Files

ApprMinkDecomp_mcs_EKT.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

612

Files downloads

309