# The ICICS/CS Reading Room

## UBC CS TR-89-18 Summary

- No on-line copy of this technical report is available.

- The Expected Capacity of Concentrators, January 1989 Nicholas Pippenger
We determine the ``expected capacity'' of a class of sparse concentrators called ``modular concentrators''. In these concentrators, each input is connected to exactly two outputs,
each output is connected to exactly three inputs, and the ``girth'' (the length of the shortest
cycle in the connexion graph) is large. We consider two definitions of expected capacity.
For the first (which is due to Masson and Morris), we assume that a batch of customers arrives at a random set of inputs and that a maximum matching of these customers to servers
at the outputs is found. The number of unsatisfied requests is negligible if customers arrive at fewer than one-half of the inputs, and it grows quite gracefully even beyond this
threshold. We also consider the situation in which customers arrive sequentially, and the
decision as to how to serve each is made randomly, without knowledge of future arrivals.
In this case, the number of unsatisfied requests is larger, but still quite modest.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.