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

DOI10.1016/j.ipl.2014.06.013zbMath1366.68097OpenAlexW1966674384MaRDI QIDQ402379

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 algorithmsbipartite matchingadvice complexitystable marriage

Mathematics Subject Classification ID

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

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