Alternative decompositions and distributed algorithms for network utility maximization

Daniel P. Palomar, Mung Chiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


Network utility maximization problems provide an important approach to conduct network resource management such as power and rate allocation. In the existing literature, distributed implementations are typically achieved by the means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements which thus far have not been fully exploited, such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents in a systematic way how to apply these decomposition techniques to network utility maximization problems. The presentation is based on a general network optimization model that unifies existing works, and then is particularized to two concrete examples of recent interest: generalized water-filling algorithms and wireless cellular downlink power control. We can thus obtain a variety of distributed algorithms with different characteristics to suit the needs of specific applications. Both primal and dual decomposition techniques are considered at many different hierarchy levels, leading to a range of choices of hybrid, multi-level, primal/dual decomposition schemes. Each particular combination provides a different distributed algorithm for resource allocation. The choice of decomposition method and distributed algorithm for a particular problem depends on factors such as the amount of signalling required for proper coordination, asymmetry of computational load, and speed of convergence.

Original languageEnglish (US)
Title of host publicationGLOBECOM'05
Subtitle of host publicationIEEE Global Telecommunications Conference, 2005
Number of pages6
StatePublished - 2005
EventGLOBECOM'05: IEEE Global Telecommunications Conference, 2005 - St. Louis, MO, United States
Duration: Nov 28 2005Dec 2 2005

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference


OtherGLOBECOM'05: IEEE Global Telecommunications Conference, 2005
Country/TerritoryUnited States
CitySt. Louis, MO

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Alternative decompositions and distributed algorithms for network utility maximization'. Together they form a unique fingerprint.

Cite this