On the advice complexity of online bipartite matching and online stable marriage
DOI10.1016/J.IPL.2014.06.013zbMATH Open1366.68097OpenAlexW1966674384MaRDI QIDQ402379FDOQ402379
Authors: Shuichi Miyazaki 
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
Recommendations
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)
Cites Work
- On-line algorithms for weighted bipartite matching and stable marriages
- On the advice complexity of the knapsack problem
- Online graph exploration with advice
- Online coloring of bipartite graphs with and without advice
- On the advice complexity of the \(k\)-server problem
- AdWords and generalized online matching
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- 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 (extended abstract)
- Measuring the problem-relevant information in input
- College Admissions and the Stability of Marriage
- Online matching with concave returns
- Title not available (Why is that?)
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- The relative worst order ratio for online algorithms
- Title not available (Why is that?)
- Online vertex-weighted bipartite matching and single-bid budgeted allocations
- Independent set with advice: the impact of graph knowledge (extended abstract)
- On advice complexity of the \(k\)-server problem under sparse metrics
- Online Computation with Advice
- On the advice complexity of buffer management
- Randomized primal-dual analysis of RANKING for online bipartite matching
Cited In (14)
- The advice complexity of a class of hard online problems
- Stable secretaries
- On the power of advice and randomization for online bipartite matching
- Minimum cost perfect matching with delays for two sources
- Minimum cost perfect matching with delays for two sources
- PROM: efficient matching query processing on high-dimensional data
- Fully Online Matching with Advice on General Bipartite Graphs and Paths
- Temporal matching
- Randomized algorithm for MPMD on two sources
- Advice complexity of adaptive priority algorithms
- Online matching in regular bipartite graphs
- Impatient Online Matching
- Advice complexity of online non-crossing matching
- Temporal matching on geometric graph data
This page was built for publication: On the advice complexity of online bipartite matching and online stable marriage
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402379)
