Loading...
Online Perfect Matching and Mobile Computing
Grove, Edward F. Kao, Ming-Yang Krishnan, P. Vitter, Jeffrey Scott
Grove, Edward F.
Kao, Ming-Yang
Krishnan, P.
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
We present a natural online perfect matching problem moti-
vated by problems in mobile computing. A total of n customers connect
and disconnect sequentially, and each customer has an associated set of
stations to which it may connect. Each station has a capacity limit. We
allow the network to preemptively switch a customer between allowed
stations to make room for a new arrival. We wish to minimize the total
number of switches required to provide service to every customer. Equiv-
alently, we wish to maintain a perfect matching between customers and
stations and minimize the lengths of the augmenting paths. We measure
performance by the worst case ratio of the number of switches made to
the minimum number required.
When each customer can be connected to at most two stations:
{ Some intuitive algorithms have lower bounds of
(n) and
(n= log n).
{ When the station capacities are 1, there is an upper bound of O(pn).
{ When customers do not disconnect and the station capacity is 1, we
achieve a competitive ratio of O(log n).
{ There is a lower bound of
(pn) when the station capacities are 2.
{ We present optimal algorithms when the station capacity is arbitrary
in special cases.
Description
The original publication is available at www.springerlink.com
Date
1995
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Verlag
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
E. F. Grove, M.-Y. Kao, P. Krishnan, and J. S. Vitter. “Online Perfect Matching and Mobile Computing,” Proceedings of the 4th Biannual Workshop on Algorithms and Data Structures (WADS ’95), Kingston, Ontario, Canada, August 1995, 194–205. http://dx.doi.org/10.1007/3-540-60220-8_62