dc.contributor.author | Grove, Edward F. | |
dc.contributor.author | Kao, Ming-Yang | |
dc.contributor.author | Krishnan, P. | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-21T21:48:10Z | |
dc.date.available | 2011-03-21T21:48:10Z | |
dc.date.issued | 1995 | |
dc.identifier.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 | |
dc.identifier.uri | http://hdl.handle.net/1808/7236 | |
dc.description | The original publication is available at www.springerlink.com | |
dc.description.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. | |
dc.language.iso | en_US | |
dc.publisher | Springer Verlag | |
dc.title | Online Perfect Matching and Mobile Computing | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1007/3-540-60220-8_62 | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |