Files in this item

FilesDescriptionFormat

application/pdf

application/pdfKELLEY-THESIS-2021.pdf (343kB)
(no description provided)PDF

Description

Title:Variations of online bipartite matching
Author(s):Kelley, Meghan
Advisor(s):Jacobson, Sheldon H
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(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.
Issue Date:2021-04-23
Type:Thesis
URI:http://hdl.handle.net/2142/110536
Rights Information:Copyright 2021 Meghan Kelley
Date Available in IDEALS:2021-09-17
Date Deposited:2021-05


This item appears in the following Collection(s)

Item Statistics