On the advice complexity of online bipartite matching and online stable marriage
From MaRDI portal
Publication:402379
DOI10.1016/j.ipl.2014.06.013zbMath1366.68097OpenAlexW1966674384MaRDI QIDQ402379
Publication date: 28 August 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/226931
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68) Online algorithms; streaming algorithms (68W27)
Related Items (11)
Minimum Cost Perfect Matching with Delays for Two Sources ⋮ Minimum cost perfect matching with delays for two sources ⋮ Online Matching in Regular Bipartite Graphs ⋮ Advice complexity of online non-crossing matching ⋮ The advice complexity of a class of hard online problems ⋮ Advice complexity of adaptive priority algorithms ⋮ Temporal matching on geometric graph data ⋮ PROM: efficient matching query processing on high-dimensional data ⋮ Stable secretaries ⋮ Temporal matching ⋮ Impatient Online Matching
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On-line algorithms for weighted bipartite matching and stable marriages
- Independent Set with Advice: The Impact of Graph Knowledge
- On Advice Complexity of the k-server Problem under Sparse Metrics
- On the Advice Complexity of the Knapsack Problem
- Online Graph Exploration with Advice
- Online Coloring of Bipartite Graphs with and without Advice
- Online Stochastic Matching: Online Actions Based on Offline Statistics
- The relative worst order ratio for online algorithms
- On the Advice Complexity of the k-Server Problem
- AdWords and generalized online matching
- Information Complexity of Online Problems
- Online Computation with Advice
- On the Advice Complexity of Online Problems
- On the Advice Complexity of Buffer Management
- On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles
- The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
- Measuring the problem-relevant information in input
- Online matching with concave returns
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals
- Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
- College Admissions and the Stability of Marriage
This page was built for publication: On the advice complexity of online bipartite matching and online stable marriage
