|
This article is cited in 3 scientific papers (total in 3 papers)
Computer science
Numerical methods for the resource allocation problem in a computer network
E. A. Vorontsovaa, A. V. Gasnikovabc, P. E. Dvurechenskiibc, A. S. Ivanovad, D. A. Pasechnyuka a Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
b Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow
c Weierstrass institute for Applied Analysis and Stochastics
d State University – Higher School of Economics
Abstract:
The resource allocation problem in computer networks with a large number of links is considered. The links are used by consumers (users), whose number can also be very large. For the dual problem, numerical optimization methods are proposed, such as the fast gradient method, the stochastic projected subgradient method, the ellipsoid method, and the random gradient extrapolation method. A convergence rate estimate is obtained for each of the methods. Algorithms for distributed computation of steps in the considered methods as applied to computer networks are described. Special attention is given to the primal-dual property of the proposed algorithms.
Key words:
resource allocation, communication networks, network utility maximization, primal-dual property, fast gradient method, stochastic projected subgradient method, ellipsoid method, random gradient extrapolation method.
Received: 29.11.2019 Revised: 10.09.2020 Accepted: 16.09.2020
Citation:
E. A. Vorontsova, A. V. Gasnikov, P. E. Dvurechenskii, A. S. Ivanova, D. A. Pasechnyuk, “Numerical methods for the resource allocation problem in a computer network”, Zh. Vychisl. Mat. Mat. Fiz., 61:2 (2021), 312–344; Comput. Math. Math. Phys., 61:2 (2021), 297–328
Linking options:
https://www.mathnet.ru/eng/zvmmf11202 https://www.mathnet.ru/eng/zvmmf/v61/i2/p312
|
Statistics & downloads: |
Abstract page: | 148 | References: | 25 |
|