Convergence study of decentralized min-cost subgraph algorithms for multicast in coded networks
Date
2014
Authors
Zhao, F.
Médard, M.
Ozdaglar, A.
Lun, D.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
IEEE Transactions on Information Theory, 2014; 60(1):410-421
Statement of Responsibility
Conference Name
Abstract
The problem of establishing minimum-cost multicast connections in coded networks can be viewed as an optimization problem, and decentralized algorithms were proposed by Lun to compute the optimal subgraph using the dual subgradient method. However, the convergence rate problem for these algorithms remains open. There are limited results in the literature, which bound the amount of infeasibility of the primal solution recovered after each iterations or the convergence rate. However, due to the special structure of the network coding problem, we have an algorithm that generates a feasible solution after each iterations. In addition, the convergence rate of the primal problem is $O(1/n)$ to a neighborhood of the optimal solution. We also propose heuristics to further improve our algorithm and demonstrate through simulations that the distributed algorithm converges to the optimal subgraph quickly and is robust against network topology changes
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2013 IEEE