On the advice complexity of online bipartite matching and online stable marriage
From MaRDI portal
Publication:402379
DOI10.1016/j.ipl.2014.06.013zbMath1366.68097MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
91B68: Matching models
68W27: Online algorithms; streaming algorithms
Related Items
Online Matching in Regular Bipartite Graphs, Impatient Online Matching, Minimum Cost Perfect Matching with Delays for Two Sources, Advice complexity of adaptive priority algorithms, Minimum cost perfect matching with delays for two sources, The advice complexity of a class of hard online problems, PROM: efficient matching query processing on high-dimensional data, Stable secretaries, Temporal matching, Advice complexity of online non-crossing matching, Temporal matching on geometric graph data
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
