Numerical methods for the resource allocation problem in networks

Authors Anastasiya Ivanova, D. A. Pasechnyuk, Pavel Dvurechensky, A. V. Gasnikov, Evgeniya A. Vorontsova

Publication date 29 September 2019

Network design and communication in computer systems (68M10) Communication networks in operations research (90B18) Convex programming (90C25) Nonlinear programming (90C30)

Abstract: In this paper, we consider the resource allocation problem in a network with a large number of connections which are used by a huge number of users. The resource allocation problem under discussion is a maximization problem with linear inequality constraints. To solve this problem we construct the dual problem and propose to use the following numerical optimization methods for the dual: a fast gradient method, a stochastic projected subgradient method, an ellipsoid method, and a random gradient extrapolation method. A special focus is made on the primal-dual analysis of these methods. For each method we estimate the convergence rate. We also provide some modifications of these methods in the setup of distributed computations, taking into account their application to networks.

This page was built for publication: Numerical methods for the resource allocation problem in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326197)