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.
Complete list of metadatas

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
Long-term archiving on : 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

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⟩

Share

Metrics

Record views

761

Files downloads

451