ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated.
If you have any questions, please contact Marianne Reed at mreed@ku.edu .
Online Perfect Matching and Mobile Computing
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 |