Variations of online bipartite matching

Kelley, Meghan

Permalink

https://hdl.handle.net/2142/110536 Copy

Description

Title

Variations of online bipartite matching

Author(s)

Kelley, Meghan

Issue Date

2021-04-23

Director of Research (if dissertation) or Advisor (if thesis)

Jacobson, Sheldon H

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• bipartite matching
• online algorithms

Abstract

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.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2021 Meghan Kelley

Owning Collections