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

Research output: Contribution to journalConference article

Abstract

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

Fingerprint

Distributed Protocol
Asymptotic analysis
Communication Protocol
Approximation algorithms
Assignment Problem
Asymptotic Analysis
Ordinary differential equations
Network protocols
Vertex of a graph
Maximum Matching
Graph in graph theory
Random Graphs
Bipartite Graph
Approximation Algorithms
Random walk
Ordinary differential equation
Receiver
Infinity
Tend

ASJC Scopus subject areas

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

Cite this

@article{2cd69485750b40429fa18b63462a5523,
title = "Asymptotic analysis of an assignment problem arising in a distributed communications protocol",
abstract = "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.",
author = "Bruce Hajek",
year = "1988",
month = "12",
day = "1",
language = "English (US)",
pages = "1455--1459",
journal = "Proceedings of the IEEE Conference on Decision and Control",
issn = "0191-2216",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

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

AU - Hajek, Bruce

PY - 1988/12/1

Y1 - 1988/12/1

N2 - 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.

AB - 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.

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

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

M3 - Conference article

AN - SCOPUS:0024170212

SP - 1455

EP - 1459

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

SN - 0191-2216

ER -