EN|RU
English version: Journal of Applied and Industrial Mathematics, 2018, 12:4, 749–758 |
![]() |
Volume 25, No 4, 2018, P. 131-148 UDC 519.16
Keywords: sum vector, search for a vector subset, approximation algorithm, inapproximability bound. DOI: 10.17377/daio.2018.25.618 Vladimir V. Shenmaier 1 Received 11 April 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. |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|