×

Approximating multidimensional subset sum and Minkowski decomposition of polygons. (English) Zbl 1409.68330

Summary: 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 1\(D\)-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)\) approximation algorithm for 2\(D\)-SS-opt, where \(n\) is the cardinality of the multiset and \(\epsilon >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\), we compute summand polygons \(A\) and \(B\), where \(Q' = A+B\) is such that some geometric function differs on \(Q\) and \(Q'\) by \(O(\epsilon\, D)\), where \(D\) is the diameter of \(Q\), or the Hausdorff distance between \(Q\) and \(Q'\) is also in \(O(\epsilon\, D)\). We conclude with experimental results based on our implementations.

MSC:

68W25 Approximation algorithms
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Abu-Salem, F., Gao, S., Lauder, A.G.B.: Factoring polynomials via polytopes. In: Proceedings of ACM Internernational Symposium on Symbolic and Algebraic Computation, po. 4–11 (2004) · Zbl 1088.68183
[2] Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54, 317–331 (1997) · Zbl 0877.68067 · doi:10.1006/jcss.1997.1472
[3] Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of ACM STOC, pp. 294–304. ACM (1993) · Zbl 1310.68083
[4] Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, USA, pp. 1073–1084. SIAM (2017) · Zbl 1423.90210
[5] Carothers, N.L.: Real Analysis. Cambridge Books Online. Cambridge University Press, Cambridge (2000) · Zbl 0997.26003
[6] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, London (2009) · Zbl 1187.68679
[7] Dinur, I., Kindler, G., Raz, R., Safra, S.: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica 23(2), 205–243 (2003) · Zbl 1049.68072 · doi:10.1007/s00493-003-0019-y
[8] Emiris, I.Z., Karasoulou, A., Tzanaki, E., Zafeirakopoulos, Z.: On the space of Minkowski summands of a convex polytope. In: 32st European Workshop on Computational Geometry (EuroCG), Book of Abstracts, pp. 35–38 (2016)
[9] Emiris, I.Z., Karasoulou, A., Tzovas, C.: Approximating multidimensional subset sum and the Minkowski decomposition of polygons. In: European Workshop on Computational Geometry (EuroCG), Book of Abstracts, pp. 119–122 (2016) · Zbl 1409.68330
[10] Emiris, I.Z., Tsigaridas, E.: Minkowski decomposition of convex lattice polygons. In: Elkadi, M., Mourrain, B., Piene, R. (eds.) Algebraic Geometry and Geometric Modeling, Mathematics and Visualization, pp. 217–236. Springer, Berlin (2006) · Zbl 1114.68071
[11] Gao, S.: Absolute irreducibility of polynomials via newton polytopes. J. Algebra 237(2), 501–520 (2001) · Zbl 0997.12001 · doi:10.1006/jabr.2000.8586
[12] Gao, S., Lauder, A.G.B.: Decomposition of polytopes and polynomials. Discrete Comput. Geom. 26(1), 89–104 (2001) · Zbl 0973.68264 · doi:10.1007/s00454-001-0024-0
[13] Henk, M., Köppe, M., Weismantel, R.: Integral decomposition of polyhedra and some applications in mixed integer programming. Math. Program. 94(2), 193–206 (2003) · Zbl 1030.90070 · doi:10.1007/s10107-002-0315-0
[14] Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975) · Zbl 0345.90049 · doi:10.1145/321906.321909
[15] Kaltofen, E., May, J.P., Yang, Z., Zhi, L.: Approximate factorization of multivariate polynomials using singular value decomposition. J. Symb. Comput. 43(5), 359–376 (2008) · Zbl 1135.12003 · doi:10.1016/j.jsc.2007.11.005
[16] Kesh, D., Mehta, S.: Polynomial irreducibility testing through Minkowski summand computation. In: Proceedings of Canadian Conference on Computational Geometry, pp. 43–46 (2008)
[17] Koiliaris, K., Xu, C.: A faster pseudopolynomial time algorithm for subset sum. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pp. 1062–1072, Philadelphia, USA, (2017). SIAM. Also available as: arXiv:1507.02318 · Zbl 1422.90046
[18] Kulik, A., Shachnai, H.: There is no EPTAS for two-dimensional knapsack. Inf. Process. Lett. 110(16), 707–710 (2010) · Zbl 1234.68153 · doi:10.1016/j.ipl.2010.05.031
[19] Magazine, M.J., Chern, M.-S.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9(2), 244–247 (1984) · Zbl 0589.90059 · doi:10.1287/moor.9.2.244
[20] Ostrowski, A.M.: On multiplication and factorization of polynomials. II. Irreducibility discussion. Aequ. Math. 14, 1–31 (1976) · Zbl 0319.13005 · doi:10.1007/BF01836201
[21] Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of an FPTAS? In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA ’99, Philadelphia, USA, pp. 820–829. SIAM (1999) · Zbl 0929.65034
[22] Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12(1), 57–74 (2000) · Zbl 1034.90014 · doi:10.1287/ijoc.12.1.57.11901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.