A stochastic algorithm for online bipartite resource allocation problems

DOI10.1016/j.cor.2016.05.004zbMath1349.90659OpenAlexW2363384901MaRDI QIDQ342502

Antoine Legrain, Patrick Jaillet

Publication date: 17 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2016.05.004

zbMATH Keywords

stochastic optimizationresource allocationprimal-dual algorithmonline optimizationadwords problemL-shaped method

Mathematics Subject Classification ID

Integer programming (90C10) Stochastic programming (90C15) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Online spatio-temporal matching in stochastic and dynamic domains ⋮ Competitive online algorithms for resource allocation over the positive semidefinite cone ⋮ Decentralized online integer programming problems with a coupling cardinality constraint ⋮ Online optimisation for ambulance routing in disaster response with partial or no information on victim conditions ⋮ Learn from history for online bipartite matching ⋮ Online generalized assignment problem with historical information

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partitioning procedures for solving mixed-variables programming problems
• An introduction to randomized algorithms
• Robust discrete optimization and network flows
• An optimal deterministic algorithm for online \(b\)-matching
• Geometry of Online Packing Linear Programs
• Model Predictive Control for Dynamic Resource Allocation
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• A Dynamic Near-Optimal Algorithm for Online Linear Programming
• Introduction to Stochastic Programming
• Online traveling salesman problems with service flexibility
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• AdWords and generalized online matching
• Online Stochastic Packing Applied to Display Ad Allocation
• Online Stochastic Matching: Beating 1-1/e
• Online Stochastic Matching: New Algorithms with Better Bounds
• Primal beats dual on online packing LPs in the random-order model
• Online bipartite matching with unknown distributions

This page was built for publication: A stochastic algorithm for online bipartite resource allocation problems