A distributed algorithm for convex network optimization problems

Stavros A. Zenios; John M. Mulvey

doi:10.1016/0167-8191(88)90004-X

A distributed algorithm for convex network optimization problems

Stavros A. Zenios, John M. Mulvey

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

Gauss-Seidel type relaxation techniques are applied in the context of strictly convex network optimization problems. The algorithm lends itself for processing in a massively distributed environment. A synchronous relaxation method (SRM) is proposed, based on the k-coloring properties of the network graph. The method is tested in a simulated distributed environment on a sequential machine. Lower bounds for the expected efficiency of SRM are developed and compared with its performance as obtained through computional experiments.

Original language	English (US)
Pages (from-to)	45-56
Number of pages	12
Journal	Parallel Computing
Volume	6
Issue number	1
DOIs	https://doi.org/10.1016/0167-8191(88)90004-X
State	Published - Jan 1988

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Computer Graphics and Computer-Aided Design
Artificial Intelligence

Keywords

Networks
distributed systems
nonlinear programming
optimization

Access to Document

10.1016/0167-8191(88)90004-X

Cite this

@article{d7aaaacce4b3445ba9e9ee0f30f3c81d,

title = "A distributed algorithm for convex network optimization problems",

abstract = "Gauss-Seidel type relaxation techniques are applied in the context of strictly convex network optimization problems. The algorithm lends itself for processing in a massively distributed environment. A synchronous relaxation method (SRM) is proposed, based on the k-coloring properties of the network graph. The method is tested in a simulated distributed environment on a sequential machine. Lower bounds for the expected efficiency of SRM are developed and compared with its performance as obtained through computional experiments.",

keywords = "Networks, distributed systems, nonlinear programming, optimization",

author = "Zenios, {Stavros A.} and Mulvey, {John M.}",

note = "Funding Information: * Research partially supported by NSF grant No. DCR-8401098 and a University of Pennsylvania Research Foundation grant.",

year = "1988",

month = jan,

doi = "10.1016/0167-8191(88)90004-X",

language = "English (US)",

volume = "6",

pages = "45--56",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A distributed algorithm for convex network optimization problems

AU - Zenios, Stavros A.

AU - Mulvey, John M.

N1 - Funding Information: * Research partially supported by NSF grant No. DCR-8401098 and a University of Pennsylvania Research Foundation grant.

PY - 1988/1

Y1 - 1988/1

N2 - Gauss-Seidel type relaxation techniques are applied in the context of strictly convex network optimization problems. The algorithm lends itself for processing in a massively distributed environment. A synchronous relaxation method (SRM) is proposed, based on the k-coloring properties of the network graph. The method is tested in a simulated distributed environment on a sequential machine. Lower bounds for the expected efficiency of SRM are developed and compared with its performance as obtained through computional experiments.

AB - Gauss-Seidel type relaxation techniques are applied in the context of strictly convex network optimization problems. The algorithm lends itself for processing in a massively distributed environment. A synchronous relaxation method (SRM) is proposed, based on the k-coloring properties of the network graph. The method is tested in a simulated distributed environment on a sequential machine. Lower bounds for the expected efficiency of SRM are developed and compared with its performance as obtained through computional experiments.

KW - Networks

KW - distributed systems

KW - nonlinear programming

KW - optimization

UR - http://www.scopus.com/inward/record.url?scp=38249032044&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249032044&partnerID=8YFLogxK

U2 - 10.1016/0167-8191(88)90004-X

DO - 10.1016/0167-8191(88)90004-X

M3 - Article

AN - SCOPUS:38249032044

SN - 0167-8191

VL - 6

SP - 45

EP - 56

JO - Parallel Computing

JF - Parallel Computing

IS - 1

ER -

A distributed algorithm for convex network optimization problems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this