{"id":{"repo_id":"rice","oai_identifier":"oai:repository.rice.edu:1911/118526"},"canonical_url":"https://search.dev.ndltd.org/etd/rice/oai:repository.rice.edu:1911/118526","repository":{"repo_id":"rice","name":"Rice University","base_url":"https://repository.rice.edu/server/oai/request"},"display":{"title":"Stochastic Assignment with Expiration","abstract":"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.","abstract_html":"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.","abstract_has_math":true,"creators":["Shapoval, Boris Alexandrovich"],"institution":"Rice University","degree_name":"Master of Arts","degree_level":"Masters","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Perez-Salazar, Sebastian"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-04-25","date_published":"2025-04-25","updated_at":"2026-07-24T04:10:24Z","subjects":["online stochastic matching","linear programming"],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1911/118526","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Perez-Salazar, Sebastian"]},{"key":"dc:creator","label":"Author","values":["Shapoval, Boris Alexandrovich"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-05-30T21:06:09Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-05-30T21:06:09Z"]},{"key":"dc:date.issued","label":"Date","values":["2025-04-25"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Arts"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Rice University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["online stochastic matching","linear programming"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1911/118526"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Stochastic Assignment with Expiration"]}]}],"canonical_facts":{"dc:contributor.advisor":["Perez-Salazar, Sebastian"],"dc:creator":["Shapoval, Boris Alexandrovich"],"dc:date.accessioned":["2025-05-30T21:06:09Z"],"dc:date.available":["2025-05-30T21:06:09Z"],"dc:date.issued":["2025-04-25"],"dc:description.abstract":["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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/1911/118526"],"dc:language.iso":["eng"],"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."],"dc:subject":["online stochastic matching","linear programming"],"dc:title":["Stochastic Assignment with Expiration"],"dc:type":["Thesis"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Arts"],"thesis:institution_name":["Rice University"]},"updated_at":"2026-07-24T04:10:24Z"}