LAUSR

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, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. Our approach relates kD-SS with the well studied closest vector problem. On the positive side, we present a $$O(n^3/\epsilon ^2)$$O(n3/ϵ2) approximation algorithm for 2D-SS-opt, where n is the cardinality of the multiset and $$\epsilon >0$$ϵ>0 bounds the additive error in terms of some property of the input. We state two variations of this algorithm, which are more suitable for implementation. Employing a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former: For an input polygon Q and parameter $$\epsilon >0$$ϵ>0, we compute summand polygons A and B, where $$Q' = A+B$$Q′=A+B is such that some geometric function differs on Q and $$Q'$$Q′ by $$O(\epsilon \, D)$$O(ϵD), where D is the diameter of Q, or the Hausdorff distance between Q and $$Q'$$Q′ is also in $$O(\epsilon \, D)$$O(ϵD). We conclude with experimental results based on our implementations.