Back to search

University of British Columbia

Online contention resolution schemes for matchings and matroids

Abstract

dc:description

We investigate the problem of designing (preferably optimal) online contention resolution schemes (OCRSs). They are a powerful framework for optimization under various combinatorial constraints such as matroids, matchings, knapsacks and their intersections. OCRSs immediately imply prophet inequalities in Bayesian online selection problem. They also have other important applications such as stochastic probing and oblivious posted price mechanisms. We present several novel OCRSs which improve the current state-of-the-art algorithms. We design an optimal 0.5-selectable OCRS over matroids with rank 2, and another optimal 0.5-selectable OCRS over transversal matroids. Previously the best result applicable to these types of matroids was a 0.25-selectable OCRS. Furthermore, we design a 1/(k+1)-selectable OCRS over matchings in k-partite hypergraphs.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ramezani, Iliad
Contributors dc:contributor
  • Shepherd, Bruce
  • Fu, Hu

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/79698

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ramezani, Iliad. Online contention resolution schemes for matchings and matroids. master's thesis, University of British Columbia, 2021. http://hdl.handle.net/2429/79698