### 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 language | English (US) |
---|---|

Pages (from-to) | 1455-1459 |

Number of pages | 5 |

Journal | Proceedings of the IEEE Conference on Decision and Control |

State | Published - Dec 1 1988 |

Event | Proceedings of the 27th IEEE Conference on Decision and Control - Austin, TX, USA Duration: Dec 7 1988 → Dec 9 1988 |

### Fingerprint

### ASJC Scopus subject areas

- Control and Systems Engineering
- Modeling and Simulation
- Control and Optimization

### Cite this

**Asymptotic analysis of an assignment problem arising in a distributed communications protocol.** / Hajek, Bruce.

Research output: Contribution to journal › Conference article

}

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 -