DSpace Repository

Serve or Skip: The Power of Rejection in Online Bottleneck Matching

Show simple item record

dc.contributor.author Anthony, Barbara M.
dc.contributor.author Chung, Christine
dc.date.accessioned 2016-11-22T15:03:25Z
dc.date.available 2016-11-22T15:03:25Z
dc.date.issued 2016-11
dc.identifier.citation Anthony, B. M., & Chung, C. (2016). Serve or skip: the power of rejection in online bottleneck matching. Journal of Combinatorial Optimization, 32(4), 1232–1253. https://doi.org/10.1007/s10878-015-9948-9 en_US
dc.identifier.uri http://hdl.handle.net/11214/128
dc.description The final publication is available at Springer via http://dx.doi.org/10.1007/s10878-015-9948-9 en_US
dc.description.abstract We consider the online matching problem, where n server-vertices lie in a metric space and n request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. We focus on the egalitarian bottleneck objective, where the goal is to minimize the maximum distance between any request and its server. It has been demonstrated that while there are effective algorithms for the utilitarian objective (minimizing total cost) in the resource augmentation setting where the offline adversary has half the resources, these are not effective for the egalitarian objective. Thus, we propose a new Serve-or-Skip bicriteria analysis model, where the online algorithm may reject or skip up to a specified number of requests, and propose two greedy algorithms: GRINN(t) and GRIN∗ (t). We show that the Serve-or-Skip model of resource augmentation analysis can essentially simulate the doubled-servercapacity model, and then examine the performance of GRINN(t) and GRIN∗ (t). en_US
dc.language.iso en_US en_US
dc.publisher Journal of Combinatorial Optimization en_US
dc.subject Online algorithms en_US
dc.subject Bottleneck matching en_US
dc.subject Resource augmentation en_US
dc.subject Approximation algorithms en_US
dc.title Serve or Skip: The Power of Rejection in Online Bottleneck Matching en_US
dc.type Article en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search


Browse

My Account

Links