{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/110536"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/110536","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Variations of online bipartite matching","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kelley, Meghan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Jacobson, Sheldon H"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09-17T01:11:11Z","date_published":"2021-09-17T01:11:11Z","updated_at":"2026-07-22T22:24:52Z","subjects":["bipartite matching","online algorithms"],"languages":["en"],"rights":["Copyright 2021 Meghan Kelley"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/110536","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jacobson, Sheldon H"]},{"key":"dc:creator","label":"Author","values":["Kelley, Meghan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-09-17T01:11:11Z","2021-04-23","2021-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["bipartite matching","online algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Meghan Kelley"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/110536"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Meghan Kelley, accepted the attached license on 2021-04-21 at 16:24.","The student, Meghan Kelley, submitted this Thesis for approval on 2021-04-21 at 16:28.","This Thesis was approved for publication on 2021-04-23 at 16:31.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16479 on 2021-09-16 at 16:46:48","Made available in DSpace on 2021-09-17T01:11:11Z (GMT). No. of bitstreams: 2 KELLEY-THESIS-2021.pdf: 343279 bytes, checksum: beb3ebb2740d6278c3b0e0678c52173a (MD5) LICENSE.txt: 4210 bytes, checksum: 08fc30b90726124ba586ba23539ef41a (MD5) Previous issue date: 2021-04-23"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Variations of online bipartite matching"]}]}],"canonical_facts":{"dc:contributor":["Jacobson, Sheldon H"],"dc:creator":["Kelley, Meghan"],"dc:date":["2021-09-17T01:11:11Z","2021-04-23","2021-05"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Meghan Kelley, accepted the attached license on 2021-04-21 at 16:24.","The student, Meghan Kelley, submitted this Thesis for approval on 2021-04-21 at 16:28.","This Thesis was approved for publication on 2021-04-23 at 16:31.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16479 on 2021-09-16 at 16:46:48","Made available in DSpace on 2021-09-17T01:11:11Z (GMT). No. of bitstreams: 2 KELLEY-THESIS-2021.pdf: 343279 bytes, checksum: beb3ebb2740d6278c3b0e0678c52173a (MD5) LICENSE.txt: 4210 bytes, checksum: 08fc30b90726124ba586ba23539ef41a (MD5) Previous issue date: 2021-04-23"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/110536"],"dc:language":["en"],"dc:rights":["Copyright 2021 Meghan Kelley"],"dc:subject":["bipartite matching","online algorithms"],"dc:title":["Variations of online bipartite matching"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}