Том 25, номер 4, 2018 г., Стр. 131-148

УДК 519.16
Шенмайер В. В.
Аппроксимируемость задачи о подмножестве векторов с суммой максимальной длины

Аннотация:
Рассматривается задача выбора подмножества векторов с суммой максимальной длины. Дан ответ на вопрос о существовании полиномиальных приближённых алгоритмов, позволяющих решать эту задачу с константной точностью при нефиксированной размерности пространства. Установлено, что в случае евклидовых пространств рассматриваемая задача разрешима за полиномиальное время с точностью $\sqrt{\alpha}$, где $\alpha = 2/\pi$, и при условии $P \ne$ NP не существует полиномиальных алгоритмов с лучшей точностью. Показано, что в случае пространств с нормой $l_p$ задача APX-полна, если $p \in [1, 2]$, и не аппроксимируема с константной точностью, если $P \ne$ NP и $p \in (2, \infty)$.
Табл. 1, библиогр. 21.

Ключевые слова: суммарный вектор, поиск подмножества векторов, приближённый алгоритм, порог неприближаемости.

DOI: 10.17377/daio.2018.25.618

Шенмайер Владимир Владимирович ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru

Статья поступила 11 апреля 2018 г.
Исправленный вариант — 13 июля 2018 г.

Литература

[1] Бабурин А. Е., Гимади Э. Х., Глебов Н. И., Пяткин А. В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискрет. анализ и исслед. операций. Сер. 2. 2007. Т. 14, № 1. С. 32–42.

[2] Бабурин А. Е., Пяткин А. В. О полиномиальных алгоритмах решения одной задачи суммирования векторов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 2. С. 3–10.

[3] Пяткин А. В. О сложности задачи выбора подмножества векторов максимальной суммарной длины // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 6. С. 68–73.

[4] Шенмайер В. В. Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 4. C. 102–115.

[5] Шенмайер В. В. Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 4. C. 111–129.

[6] Шенмайер В. В. Сложность и аппроксимация задачи о длиннейшем суммарном векторе // Журн. вычисл. математики и мат. физики. 2018. Т. 58, № 6. С. 883–889.

[7] Alon N., Naor A. Approximating the cut-norm via Grothendieck’s inequality // SIAM J. Comput. 2006. Vol. 35, No. 4. P. 787–803.

[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). Philadelphia, PA: SIAM, 2011. P. 497–511.

[9] Briët J., Regev O., Saket R. Tight hardness of the non-commutative Grothendieck problem // Theory Comput. 2017. Vol. 13, No. 15. P. 1–24.

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

[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). Cham: Springer, 2016. P. 159–170. (Lect. Notes Comput. Sci.; Vol. 9869).

[12] Grothendieck A. Résumé de la théorie métrique des produits tensoriels topologiques // Bol. Soc. Mát. São Paulo. 1953. Vol. 8. P. 1–79.

[13] Hwang F. K., Onn S., Rothblum U. G. A polynomial time algorithm for shaped partition problems // SIAM J. Optim. 1999. Vol. 10, No. 1. P. 70–81.

[14] Matou$\check{s}$ek J. Lectures on discrete geometry. New York: Springer, 2002.

[15] Nesterov Yu. Semidefinite relaxation and nonconvex quadratic optimization // Optim. Methods Softw. 1998. Vol. 9, No. 1–3. P. 141–160.

[16] Nesterov Yu. Global quadratic optimization via conic relaxation // Handbook of semidefinite programming. Boston: Kluwer Acad. Publ., 2000. P. 363–387.

[17] Onn S., Schulman L. J. The vector partition problem for convex objective functions // Math. Oper. Res. 2001. Vol. 26, No. 3. P. 583–590.

[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). New York: ACM, 2006. P. 447–456.

[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). Cham: Springer, 2017. P. 469–480. (Lect. Notes Comput. Sci; Vol. 10392).

[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). Cham: Springer, 2018. P. 41–51. (Lect. Notes Comput. Sci.; Vol. 10787).

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