About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:4, 749–758
Volume 25, No 4, 2018, P. 131-148
UDC 519.16
V. V. Shenmaier
Approximability of the problem of finding a vector subset with the longest sum
Abstract:
We answer the question of existence of polynomial-time constant-factor approximation algorithms for the space of nonfixed dimension. We prove that, in Euclidean space the problem is solvable in polynomial time with accuracy $\sqrt{\alpha}$, where $\alpha = 2/\pi$, and if $P \ne$ NP then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the $l_p$ spaces, the problem is APX-complete if $p \in [1, 2]$ and not approximable with constant accuracy if $P \ne$ NP and $p \in (2, \infty)$.
Tab. 1, bibliogr. 21.
Keywords: sum vector, search for a vector subset, approximation algorithm, inapproximability bound.
DOI: 10.17377/daio.2018.25.618
Vladimir V. Shenmaier 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: shenmaier@mail.ru
Received 11 April 2018
Revised 13 July 2018
References
[1] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, The problem of finding a subset of vectors with the maximum total weight, Diskretn. Anal. Issled. Oper., Ser. 2, 14, No. 1, 32–42, 2007 [Russian]. Translated in J. Appl. Ind. Math., 2, No. 1, 32–38, 2008.[2] A. E. Baburin and A. V. Pyatkin, Polynomial algorithms for solving the vector sum problem, Diskretn. Anal. Issled. Oper., Ser. 1, 13, No. 2, 3–10, 2006 [Russian]. Translated in J. Appl. Ind. Math., 1, No. 3, 268–272, 2007.
[3] A. V. Pyatkin, On complexity of a choice problem of the vector subset with the maximum sum length, Diskretn. Anal. Issled. Oper., 16, No. 6, 68–73, 2009 [Russian]. Translated in J. Appl. Ind. Math., 4, No. 4, 549–552, 2010.
[4] V. V. Shenmaier, Solving some vector subset problems by Voronoi diagrams, Diskretn. Anal. Issled. Oper., 23, No. 4, 102–115, 2016 [Russian]. Translated in J. Appl. Ind. Math., 10, No. 4, 560–566, 2016.
[5] V. V. Shenmaier, An exact algorithm for finding a vector subset with the longest sum, Diskretn. Anal. Issled. Oper., 24, No. 4, 111–129, 2017 [Russian]. Translated in J. Appl. Ind. Math., 11, No. 4, 584–593, 2017.
[6] V. V. Shenmaier, Complexity and approximation of finding the longest vector sum, Zh. Vychisl. Mat. Mat. Fiz., 58, No. 6, 883–889, 2018 [Russian]. Translated in Comput. Math. Math. Phys., 58, No. 6, 850–857, 2018.
[7] N. Alon and A. Naor, Approximating the cut-norm via Grothendieck’s inequality, SIAM J. Comput., 35, No. 4, 787–803, 2006.
[8] A. Bhaskara and A. Vijayaraghavan, Approximating matrix $p$-norms, in Proc. 22nd Annu. ACM-SIAM Symp. Discrete Algorithms, San Francisco, USA, Jan. 23–25, 2011, pp. 497–511, SIAM, Philadelphia, PA, 2011.
[9] J. Briët, O. Regev, and R. Saket, Tight hardness of the non-commutative Grothendieck problem, Theory Comput., 13, No. 15, 1–24, 2017.
[10] B. Gärtner and J. Matoušek, Approximation Algorithms and Semidefinite Programming, Springer, Heidelberg, 2012.
[11] E. Kh. Gimadi and I. A. Rykov, Efficient randomized algorithms for a vector subset problem, in Discrete Optimization and Operations Research (Proc. 9th Int. Conf. DOOR, Vladivostok, Russia, Sept. 19–23, 2016),
pp. 159–170, Springer, Cham, 2016 (Lect. Notes Comput. Sci., Vol. 9869).
[12] A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques, Bol. Soc. Mát. São Paulo, 8, 1–79, 1953 [French].
[13] F. K. Hwang, S. Onn, and U. G. Rothblum, A polynomial time algorithm for shaped partition problems, SIAM J. Optim., 10, No. 1, 70–81, 1999.
[14] J. Matoušek, Lectures on Discrete Geometry, Springer, New York, 2002.
[15] Yu. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw., 9, No. 1–3, 141–160, 1998.
[16] Yu. Nesterov, Global quadratic optimization via conic relaxation, in Handbook of Semidefinite Programming, pp. 363–387, Kluwer Acad. Publ., Boston, 2000.
[17] S. Onn and L. J. Schulman, The vector partition problem for convex objective functions, Math. Oper. Res., 26, No. 3, 583–590, 2001.
[18] O. Regev and R. Rosen, Lattice problems and norm embeddings, in Proc. 38th Annu. ACM Symp. Theory Comput., Seattle, USA, May 21–23, 2006, pp. 447–456, ACM, New York, 2006.
[19] V. V. Shenmaier, Complexity and algorithms for finding a subset of vectors with the longest sum, in Computing and Combinatorics (Proc. 23rd Int. Conf. COCOON 2017, Hong Kong, China, Aug. 3–5, 2017), pp. 469–480, Springer, Cham, 2017 (Lect. Notes Comput. Sci., Vol. 10392).
[20] V. V. Shenmaier, Complexity and approximation of the longest vector sum problem, in Approximation and Online Algorithms (Revis. Sel. Pap. 15th Workshop WAOA 2017, Vienna, Austria, Sept. 7–8, 2017),
[21] D. Steinberg, Computation of matrix norms with applications to robust optimization, Res. Thesis, Technion — Isr. Inst. Technol., Haifa, 2005.
