Abstract
We introduce a randomized approximation algorithm for NP-hard problem of finding a subset of m vectors chosen from n given vectors in multidimensional Euclidean space \(\mathbb {R}^k\) such that the norm of the corresponding sum-vector is maximum. We derive the relation between algorithm’s time complexity, relative error and failure probability parameters. We show that the algorithm implements Polynomial-time Randomized Approximation Scheme (PRAS) for the general case of the problem. Choosing particular parameters of the algorithm one can obtain asymptotically exact algorithm with significantly lower time complexity compared to known exact algorithm. Another set of parameters provides polynomial-time 1 / 2-approximation algorithm for the problem. We also show that the algorithm is applicable for the related (minimization) clustering problem allowing to obtain better performance guarantees than existing algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)
Baburin, A.E., Gimadi, E.K., Glebov, N.I., Pyatkin, A.V.: The problem of finding a subset of vectors with the maximum total weight. J. Appl. Ind. Math. 2(1), 32–38 (2008)
Baburin, A.E., Pyatkin, A.V.: Polynomial algorithms for solving the vector sum problem. J. Appl. Ind. Math. 1(3), 268–272 (2007)
Gimadi, E.K., Glazkov, Y.V., Rykov, I.A.: On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean space. J. Appl. Ind. Math. 3(3), 343–352 (2009)
Gimadi, E.K., Kel’manov, A.V., Kel’manova, M.A., Khamidullin, S.A.: A posteriori detection of a quasiperiodic fragment in a numerical sequence. Pattern Recogn. Image Anal. 18(1), 30–42 (2008)
Gimadi, E.K., Pyatkin, A.V., Rykov, I.A.: On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension. J. Appl. Ind. Math. 4(1), 48–53 (2010)
Dolgushev, A.V., Kel’manov, A.V.: An approximation algorithm for solving a problem of cluster analysis. J. Appl. Ind. Math. 5(4), 551–558 (2011)
Li, S.: Concise formulas for the area and volume of a hyperspherical cap. asian J. Math. Stat. 4(1), 66–70 (2011)
Acknowledgments
The authors are supported by the RSCF grant 16-11-10041.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Gimadi, E., Rykov, I. (2016). Efficient Randomized Algorithm for a Vector Subset Problem. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds) Discrete Optimization and Operations Research. DOOR 2016. Lecture Notes in Computer Science(), vol 9869. Springer, Cham. https://doi.org/10.1007/978-3-319-44914-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-44914-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44913-5
Online ISBN: 978-3-319-44914-2
eBook Packages: Computer ScienceComputer Science (R0)