Approximation algorithms for stochastic online matching with reusable resources

DOI10.1007/S00186-023-00822-3MaRDI QIDQ6046972zbMATH OpenFDO

Authors Meghan Shanks, Ge Yu, Sheldon H. Jacobson

Publication date 6 September 2023

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

zbMATH Keywords

online algorithmsapproximation algorithmsreusable resourcesstochastic matching

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Stochastic programming (90C15)

Recommendations

• Online stochastic weighted matching: improved approximation algorithms
• Online total bipartite matching problem
• Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation
• Online stochastic matching: new algorithms and bounds

Cites work

• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• A Sequential Stochastic Assignment Problem
• A Sequential Stochastic Assignment Problem in a Partially Observable Markov Chain
• A markov chain version of the secretary problem
• A stochastic assignment problem
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Approximate Dynamic Programming
• Fundamentals of queueing theory
• Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities
• Hiring secretaries over time: the benefit of concurrent employment
• Markov decision processes and stochastic games with total effective payoff
• On-line scheduling of jobs with fixed start and end times
• Online C-benevolent job scheduling on multiple machines
• Online Stochastic Matching: Beating 1-1/e
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online interval scheduling: Randomized and multiprocessor cases
• Online scheduling of jobs with fixed start times on related machines
• Optimal Sequential Assignment
• Optimal Sequential Assignments with Random Arrival Times
• Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model
• Randomized online interval scheduling
• Semiamarts and finite values
• Stochastic sequential decision-making with a random number of jobs
• The Temp Secretary Problem

Cited in

(4)

• scientific article; zbMATH DE number 7053386 (Why is no real title available?)
• Technical note -- Greedy algorithm for multiway matching with bounded regret
• Admission control to minimize rejections and online set cover with repetitions
• Randomized approximation and online algorithms for assignment problems

This page was built for publication: Approximation algorithms for stochastic online matching with reusable resources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046972)