Geodesic
Approximability of the problem of finding a~vector subset with the longest sum
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 131-148.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\mathrm P\neq\mathrm{NP}$ then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the $\ell_p$ spaces, the problem is APX-complete if $p\in[1,2]$ and not approximable with constant accuracy if $\mathrm P\neq\mathrm{NP}$ and $p\in(2,\infty)$. Tab. 1, bibliogr. 21.
Keywords: sum vector, search for a vector subset, approximation algorithm, inapproximability bound. 
@article{DA_2018_25_4_a8,
     author = {V. V. Shenmaier},
     title = {Approximability of the problem of finding a~vector subset with the longest sum},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {131--148},
     publisher = {mathdoc},
     volume = {25},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_4_a8/}
}
TY  - JOUR
AU  - V. V. Shenmaier
TI  - Approximability of the problem of finding a~vector subset with the longest sum
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 131
EP  - 148
VL  - 25
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_4_a8/
LA  - ru
ID  - DA_2018_25_4_a8
ER  - 
%0 Journal Article
%A V. V. Shenmaier
%T Approximability of the problem of finding a~vector subset with the longest sum
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 131-148
%V 25
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_4_a8/
%G ru
%F DA_2018_25_4_a8
V. V. Shenmaier. Approximability of the problem of finding a~vector subset with the longest sum. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 131-148. http://geodesic.mathdoc.fr/item/DA_2018_25_4_a8/

[1] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38 | DOI | MR | Zbl

[2] A. E. Baburin, A. V. Pyatkin, “Polynomial algorithms for solving the vector sum problem”, J. Appl. Ind. Math., 1:3 (2007), 268–272 | DOI | MR | MR | Zbl

[3] A. V. Pyatkin, “On complexity of a choice problem of the vector subset with the maximum sum length”, J. Appl. Ind. Math., 4:4 (2010), 549–552 | DOI | MR | Zbl

[4] V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Ind. Math., 10:4 (2016), 560–566 | DOI | DOI | MR | Zbl

[5] V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Ind. Math., 11:4 (2017), 584–593 | DOI | DOI | MR | Zbl

[6] V. V. Shenmaier, “Complexity and approximation of finding the longest vector sum”, Comput. Math. Math. Phys., 58:6 (2018), 850–857 | DOI | DOI | MR | Zbl

[7] Alon N., Naor A., “Approximating the cut-norm via Grothendieck's inequality”, SIAM J. Comput., 35:4 (2006), 787–803 | DOI | MR | Zbl

[8] Bhaskara A., Vijayaraghavan A., “Approximating matrix $p$-norms”, Proc. 22nd Annu. ACM-SIAM Symp. Discrete Algorithms, SODA 2011 (San Francisco, CA, Jan. 23–25, 2011), SIAM, Philadelphia, PA, 2011, 497–511 | DOI | MR | Zbl

[9] Briët J., Regev O., Saket R., “Tight hardness of the non-commutative Grothendieck problem”, Theory Comput., 13:15 (2017), 1–24 | DOI | MR

[10] Gärtner B., Matoušek J., Approximation algorithms and semidefinite programming, Springer, Heidelberg, 2012 | MR | Zbl

[11] Gimadi E. Kh., Rykov I. A., “Efficient randomized algorithms for a vector subset problem/”, Proc. 9th Int. Conf. Discrete Optimization and Operations Research, DOOR 2016 (Vladivostok, Sep. 19–23, 2016), Lect. Notes Comput. Sci., 9869, Springer, Cham, 2016, 159–170 | DOI | MR

[12] Grothendieck A., “Résumé de la théorie métrique des produits tensoriels topologiques”, Bol. Soc. Mát. São Paulo, 8 (1953), 1–79 | MR

[13] Hwang F. K., Onn S., Rothblum U. G., “A polynomial time algorithm for shaped partition problems”, SIAM J. Optim., 10:1 (1999), 70–81 | DOI | MR | Zbl

[14] Matoušek J., Lectures on discrete geometry, Springer, New York, 2002 | MR | Zbl

[15] Nesterov Yu., “Semidefinite relaxation and nonconvex quadratic optimization”, Optim. Methods Softw., 9:1–3 (1998), 141–160 | DOI | MR | Zbl

[16] Nesterov Yu., “Global quadratic optimization via conic relaxation”, Handbook of semidefinite programming, Kluwer Acad. Publ., Boston, 2000, 363–387 | MR

[17] Onn S., Schulman L. J., “The vector partition problem for convex objective functions”, Math. Oper. Res., 26:3 (2001), 583–590 | DOI | MR | Zbl

[18] Regev O., Rosen R., “Lattice problems and norm embeddings”, Proc. 38th Annu. ACM Symp. Theory Comput., STOC 2006 (Seattle, WA, May 21–23, 2006), ACM, New York, 2006, 447–456 | MR | Zbl

[19] Shenmaier V. V., “Complexity and algorithms for finding a subset of vectors with the longest sum”, Proc. 23rd Computing and Combinatorics Conf., COCOON 2017 (Hong Kong, Aug. 3–5, 2017), Lect. Notes Comput. Sci., 10392, Springer, Cham, 2017, 469–480 | DOI | MR | Zbl

[20] Shenmaier V. V., “Complexity and approximation of the longest vector sum problem”, Proc. 15th Workshop Approximation and Online Algorithms, WAOA 2017 (Vienna, Austria, Sep. 7–8, 2017), Lect. Notes Comput. Sci., 10787, Springer, Cham, 2018, 41–51 | DOI | MR | Zbl

[21] Steinberg D., Computation of matrix norms with applications to robust optimization, Res. Thes., Technion – Isr. Inst. Technology, Haifa, 2005