NDLI: Serve or skip: the power of rejection in online bottleneck matching

Content Provider	Springer Nature Link
Author	Anthony, Barbara M. Chung, Christine
Copyright Year	2015
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 shown 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 (SoS) 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 $${{\textsc {Grin}}^(t)}$$ . We show that the SoS model of resource augmentation analysis can essentially simulate the doubled-server-capacity model, and then examine the performance of GriNN(t) and $${\textsc {Grin}^(t)}$$ .
Starting Page	1232
Ending Page	1253
Page Count	22
File Format	PDF
ISSN	13826905
Journal	Journal of Combinatorial Optimization
Volume Number	32
Issue Number	4
e-ISSN	15732886
Language	English
Publisher	Springer US
Publisher Date	2015-09-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Online algorithms Bottleneck matching Resource augmentation Approximation algorithms Matching Combinatorics Convex and Discrete Geometry Mathematical Modeling and Industrial Mathematics Theory of Computation Optimization Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization Discrete Mathematics and Combinatorics Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Online bottleneck matching

Online tree node assignment with resource augmentation

The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation

1.61-approximation for min-power strong connectivity with two power levels

Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints

(1+ε)-competitive algorithm for online OVSF code assignment with resource augmentation

Approximation Algorithms in Batch Processing

Approximation Algorithms for Quadratic Programming

Scheduling with release times and rejection on two parallel machines

Serve or skip: the power of rejection in online bottleneck matching

Similar Documents

Online bottleneck matching

Online tree node assignment with resource augmentation

The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation

1.61-approximation for min-power strong connectivity with two power levels

Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints

(1+ε)-competitive algorithm for online OVSF code assignment with resource augmentation

Approximation Algorithms in Batch Processing

Approximation Algorithms for Quadratic Programming

Scheduling with release times and rejection on two parallel machines

Serve or skip: the power of rejection in online bottleneck matching