Stochastic Assignment with Expiration

This thesis introduces a capacitated online stochastic bipartite matching problem, where offline nodes may be matched multiple times and expire at unknown stochastic times. This problem is PSPACE hard; thus we first focus on the subproblem where each offline node can be matched at most once and aim to develop algorithms that achieve large expected overall values from the matchings. A decision maker (DM) must balance obtaining a matching reward now and keeping enough possibilities for the future with possible expirations. Since this problem is intractable, we first provide a compact linear program (LP) formulation that upper bounds the expected value of an optimal algorithm. Based on this LP, we design a polynomial-time algorithm that guarantees an expected value of at least a $1 - 1/e$ fraction of the optimal expected value. We demonstrate the tightness of our LP-based analysis by providing tight integrality gaps as well as worst-case instances. Returning to the capacitated problem, we provide another LP relaxation. We generalize our previous algorithms to evaluate their numerical performance on the harder, capacitated problem. We observe that some natural ideas do not generalize, while others seem to remain competitive.

Name thesis:degree_name

Master of Arts

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

2025

Author dc:creator

• Shapoval, Boris Alexandrovich

Advisor dc:contributor.advisor

• Perez-Salazar, Sebastian

• online stochastic matching
• linear programming

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/118526

OAI identifier oai:identifier

oai:repository.rice.edu:1911/118526