@inproceedings{f6c8e47bc96f44a58263034ec23aac57,
title = "Online perfect matching and mobile computing",
abstract = "We present a natural online perfect matching problem motivated 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 (Formula Presented) and (Formula Presented). When the station capacities are 1, there is an upper bound of (Formula Presented). When customers do not disconnect and the station capacity is 1, we achieve a competitive ratio of (Formula Presented). There is a lower bound of (Formula Presented) when the station capacities are 2. We present optimal algorithms when the station capacity is arbitrary in special cases.",
author = "Grove, {Edward F.} and Kao, {Ming Yang} and P. Krishnan and Vitter, {Jeffrey Scott}",
note = "Publisher Copyright: {\textcopyright} 1995, Springer-Verlag. All rights reserved.; 4th Workshop on Algorithms and Data Structures, WADS 1995 ; Conference date: 16-08-1995 Through 18-08-1995",
year = "1995",
doi = "10.1007/3-540-60220-8_62",
language = "English (US)",
isbn = "3540602208",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "194--205",
editor = "Akl, {Selim G.} and Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro",
booktitle = "Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings",
}