Online perfect matching and mobile computing

Edward F. Grove, Ming Yang Kao, P. Krishnan, Jeffrey Scott Vitter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings
EditorsSelim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540602208, 9783540602200
StatePublished - 1995
Event4th Workshop on Algorithms and Data Structures, WADS 1995 - Kingston, Canada
Duration: Aug 16 1995Aug 18 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th Workshop on Algorithms and Data Structures, WADS 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Online perfect matching and mobile computing'. Together they form a unique fingerprint.

Cite this