Asymptotic analysis of an assignment problem arising in a distributed communications protocol

Research output: Contribution to journalConference article


Matchings for a random bipartite graph are considered. Each of the αM nodes on one side of the graph is directly connected to Q nodes chosen randomly and uniformly from among the M nodes on the other side of the graph. The size matchings found by two simple approximation algorithms, as well as the size of the maximum matching when Q = 2, are asymptotically determined in the limit as Q tends to infinity with α fixed. The work is motivated by a distributed communications protocol for accessing a silent receiver. The theory of approximating slow Markov random walks by ordinary differential equations is used for the analysis.

Original languageEnglish (US)
Pages (from-to)1455-1459
Number of pages5
JournalProceedings of the IEEE Conference on Decision and Control
StatePublished - Dec 1 1988
EventProceedings of the 27th IEEE Conference on Decision and Control - Austin, TX, USA
Duration: Dec 7 1988Dec 9 1988


ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Cite this