1995 | ReviewPaper | Buchkapitel
Online perfect matching and mobile computing
verfasst von : Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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. Equivalently, 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(√n).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 Ω(√n) when the station capacities are 2.We present optimal algorithms when the station capacity is arbitrary in special cases.