Variations of online bipartite matching

The Online Bipartite Matching Problem is a well-studied problem in theoretical computer science that models several real-world applications including online investment, kidney transplantation, aviation security passenger screening, and enhanced Ebola entry screening. However, the original version of the problem is too simplistic to cover many real-world applications. Therefore it is common to consider variations of the problem that more closely model the target application. This thesis considers two variations of the problem motivated by aviation security passenger screening. The first, known as the online total bipartite matching problem, is a variation in which jobs must be assigned to some worker regardless of whether or not it is adjacent to an available worker. Tight upper and lower bounds are given for the general version of this problem, along with 1-competitive algorithm for a special case of the problem. The second variation begins with the well-known Stochastic Sequential Assignment Problem, which is a variation of the Online Bipartite Matching problem in which edge weights are calculated as the product of a job value and worker value. It extends this to the Reusable Sequential Stochastic Assignment Problem, in which workers can be reused after they finish processing a job. We consider both the stochastic and random arrival model and provide algorithms with constant approximation ratios when job lengths are constant.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2021

Author dc:creator

• Kelley, Meghan

Contributors dc:contributor

• Jacobson, Sheldon H

• bipartite matching
• online algorithms

Statement dc:rights

• Copyright 2021 Meghan Kelley

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/110536

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/110536