Approximability of the Problem of Finding a Vector Subset with the Longest Sum
Tóm tắt
Từ khóa
Tài liệu tham khảo
V. V. Shenmaier, “An Exact Algorithm for Finding a Vector Subset with the Longest Sum,” Diskretn. Anal. Issled. Oper. 24 (4), 111–129 (2017) [J. Appl. Indust. Math. 11 (4), 584–593 (2017)].
A. V. Pyatkin, “On Complexity of a Choice Problem of the Vector Subset with the Maximum Sum Length,” Diskretn. Anal. Issled. Oper. 16 (6), 68–73 (2009) [J. Appl. Indust. Math. 4 (4), 549–552 (2010)].
V. V. Shenmaier, “Complexity and Approximation of Finding the Longest Vector Sum,” Zh. Vychisl. Mat. Mat. Fiz. 58 (6), 883–889 (2018) [Comput. Math. Math. Phys. 58 (6), 850–857 (2018)].
V. V. Shenmaier, “Complexity and Algorithms for Finding a Subset of Vectors with the Longest Sum,” in Computing and Combinatorics (Proceedings. 23rd International Conference COCOON 2017,Hong Kong, China, August 3–5, 2017) (Springer, Cham, 2017), pp. 469–480.
A. E. Baburin and A. V. Pyatkin, “Polynomial Algorithms for Solving the Vector Sum Problem,” Diskretn. Anal. Issled. Oper. Ser. 1, 13 (2), 3–10 (2006) [J. Appl. Indust. Math. 1 (3), 268–272 (2007)].
F. K. Hwang, S. Onn, and U. G. Rothblum, “A Polynomial Time Algorithm for Shaped Partition Problems,” SIAM J. Optim. 10 (1), 70–81 (1999).
S. Onn and L. J. Schulman, “The Vector Partition Problem for Convex Objective Functions,” Math. Oper. Res. 26 (3), 583–590 (2001).
A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, “The Problem of Finding a Subset of Vectors with theMaximum TotalWeight,” Diskretn. Anal. Issled. Oper. Ser. 2,14 (1), 32–42 (2007) [J. Appl. Indust. Math. 2 (1), 32–38 (2008)].
E. Kh. Gimadi and I. A. Rykov, “Efficient Randomized Algorithms for a Vector Subset Problem,” in Discrete Optimization and Operations Research (Proceedings. 9th International Conference DOOR, Vladivostok, Russia, September 19–23, 2016) (Springer, Cham, 2016), pp. 159–170.
V. V. Shenmaier, “Complexity and Approximation of the Longest Vector Sum Problem, in Approximation and Online Algorithms (Revised Selected Papers. 15th Workshop WAOA 2017, Vienna, Austria, September 7–8, 2017) (Springer, Cham, 2018), pp. 41–51.
N. Alon and A. Naor, “Approximating the Cut-Norm via Grothendieck’s Inequality,” SIAM J. Comput. 35 (4), 787–803 (2006).
A. Bhaskara and A. Vijayaraghavan, “Approximating Matrix p-Norms,” in Proceedings. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, USA, January 23–25, 2011) (SIAM, Philadelphia, PA, 2011), pp. 497–511.
A. Grothendieck, “Résuméde la théorie métrique des produits tensoriels topologiques,” Bol. Soc. Mát. Sa˜ o Paulo 8, 1–79 (1953).
B. Gärtner and J. Matoušek, Approximation Algorithms and Semidefinite Programming (Springer, Heidelberg, 2012).
J. Briët, O. Regev, and R. Saket, “Tight Hardness of the Non-Commutative Grothendieck Problem,” Theory Comput. 13 (15), 1–24 (2017).
Yu. Nesterov, “Semidefinite Relaxation and Nonconvex Quadratic Optimization,” Optim. Methods Softw. 9 (1–3), 141–160 (1998).
D. Steinberg, “Computation of Matrix Norms with Applications to Robust Optimization,” Res. Thesis (Technion—Israel. Inst. Technol., Haifa, 2005).
Yu. Nesterov, “Global Quadratic Optimization via Conic Relaxation,” in Handbook of Semidefinite Programming (Kluwer Acad. Publ., Boston, 2000), pp. 363–387.
O. Regev and R. Rosen, “Lattice Problems and Norm Embeddings,” in Proceedings. 38th Annual ACM Symposium on Theory of Computing, Seattle, USA, May 21–23, 2006 (ACM, New York, 2006), pp. 447–456.
V. V. Shenmaier, “Solving Some Vector Subset Problems by Voronoi Diagrams,” Diskretn. Anal. Issled. Oper. 23 (4), 102–115 (2016) [J. Appl. Indust. Math. 10 (4), 560–566 (2016)].