Second-Order Greedy Algorithms for Centralized Teleprocessing Network Design

A. Kershenbaum, R. Boorstyn, R. Oppenheim

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


We consider the problem of designing a centralized telecommunication network comprised of multipoint lines given a set of terminal locations, traffic requirements, and a common central site. The optimal solution to this problem is a capacitated minimal spanning tree. We develop a class of heuristic algorithms for the solution of this problem by imbedding existing heuristics, referred to as first-order greedy algorithms, inside a loop where small, carefully chosen sets of arcs are alternately forced in and out of the solution. The resultant procedure is shown to be superior to existing techniques, producing solutions typically 2 percent better, while requiring only a modest amount of additional computer time.

Original languageEnglish (US)
Pages (from-to)1835-1838
Number of pages4
JournalIEEE Transactions on Communications
Issue number10
StatePublished - Oct 1980

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'Second-Order Greedy Algorithms for Centralized Teleprocessing Network Design'. Together they form a unique fingerprint.

Cite this