Online Stochastic Matching: Beating 1-1/e

DOI10.1109/FOCS.2009.72MaRDI QIDQ5171168zbMATH OpenOpenAlexFDO

Authors

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.72

Mathematics Subject Classification ID

Internet topics (68M11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cited in

(59)

• Online algorithms with advice for the dual bin packing problem
• Near optimal algorithms for online weighted bipartite matching in adversary model
• On extensions of the deterministic online model for bipartite matching and max-sat
• Online algorithms for maximum cardinality matching with edge arrivals
• On the on-line maintenance scheduling problem
• New online algorithms for story scheduling in web advertising
• A polyhedral approach to online bipartite matching
• Online stochastic matching: new algorithms and bounds
• Learn from history for online bipartite matching
• Online total bipartite matching problem
• Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model
• Primal-dual analysis for online interval scheduling problems
• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Auctions with online supply
• Strategyproof mechanisms for competitive influence in networks
• Advice complexity of online non-crossing matching
• Markovian online matching algorithms on large bipartite random graphs
• Approximation algorithms for stochastic combinatorial optimization problems
• A dynamic near-optimal algorithm for online linear programming
• Bicriteria online matching: maximizing weight and cardinality
• A Polyhedral Approach to Online Bipartite Matching
• A stochastic algorithm for online bipartite resource allocation problems
• Two-sided online bipartite matching and vertex cover: beating the greedy algorithm
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Frequency capping in online advertising
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• Tractable equilibria in sponsored search with endogenous budgets
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Budget-management strategies in repeated auctions
• Greedy bipartite matching in random type Poisson arrival model
• Technical note -- Assortment planning for two-sided sequential matching markets
• Multiplicative Pacing Equilibria in Auction Markets
• Greedy matching in bipartite random graphs
• Asymptotic analysis for multi-objective sequential stochastic assignment problems
• Online matching in regular bipartite graphs
• Stochastic online metric matching
• Dynamic stochastic matching under limited time
• Dynamic Relaxations for Online Bipartite Matching
• Online algorithms for maximum cardinality matching with edge arrivals
• On matching and thickness in heterogeneous dynamic markets
• Online stochastic matching: new algorithms with better bounds
• scientific article; zbMATH DE number 7053386 (Why is no real title available?)
• An Experimental Study of Algorithms for Online Bipartite Matching
• Approximation algorithms for stochastic online matching with reusable resources
• Online stochastic weighted matching algorithm for real‐time shared parking
• Edge-weighted online bipartite matching
• Adwords in a panorama
• Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue
• Online matching with stochastic rewards: advanced analyses using configuration linear programs
• Improved competitive ratio for edge-weighted online stochastic matching
• Two-sided capacitated submodular maximization in gig platforms
• Station assignment with reallocation
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Near-optimal algorithms for stochastic online bin packing
• Online stochastic matching with edge arrivals
• Online matching meets sampling without replacement
• Optimal online bipartite matching in degree-2 graphs
• Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching

This page was built for publication: Online Stochastic Matching: Beating 1-1/e

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