On the advice complexity of online bipartite matching and online stable marriage

DOI10.1016/J.IPL.2014.06.013MaRDI QIDQ402379zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

online algorithmsadvice complexitybipartite matchingstable marriage

Mathematics Subject Classification ID

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)

Recommendations

• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• Online matching in regular bipartite graphs
• On the power of advice and randomization for online bipartite matching
• scientific article; zbMATH DE number 176778
• On the Advice Complexity of Online Problems

Cites work

• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• scientific article; zbMATH DE number 1306855 (Why is no real title available?)
• AdWords and generalized online matching
• College Admissions and the Stability of Marriage
• Independent set with advice: the impact of graph knowledge (extended abstract)
• Information complexity of online problems
• Measuring the problem-relevant information in input
• On advice complexity of the \(k\)-server problem under sparse metrics
• On the Advice Complexity of Online Problems
• On the advice complexity of buffer management
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the knapsack problem
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• On-line algorithms for weighted bipartite matching and stable marriages
• Online Computation with Advice
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online coloring of bipartite graphs with and without advice
• Online graph exploration with advice
• Online matching with concave returns
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Randomized primal-dual analysis of RANKING for online bipartite matching
• The relative worst order ratio for online algorithms
• The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)

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
• PROM: efficient matching query processing on high-dimensional data
• Minimum cost perfect matching with delays for two sources
• 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)