On the advice complexity of online bipartite matching and online stable marriage
type: Item
instance of: scholarly article
title: On the advice complexity of online bipartite matching and online stable marriage
zbMATH Open document ID: 1366.68097
author: Shuichi Miyazaki
published in: Information Processing Letters
publication date: 2014-08-28T00:00:00Z
full work available at URL: http://hdl.handle.net/2433/226931
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 91B68
zbMATH DE Number: 6335103
zbMATH Keywords: online algorithms
zbMATH Keywords: advice complexity
zbMATH Keywords: bipartite matching
zbMATH Keywords: stable marriage
MaRDI profile type: Publication
OpenAlex ID: W1966674384
cites work: Q5365114
cites work: Online Coloring of Bipartite Graphs with and without Advice
cites work: On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles
cites work: The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
cites work: On the Advice Complexity of the k-Server Problem
cites work: On the Advice Complexity of Online Problems
cites work: On the Advice Complexity of the Knapsack Problem
cites work: The relative worst order ratio for online algorithms
cites work: Online matching with concave returns
cites work: Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
cites work: Measuring the problem-relevant information in input
cites work: Independent Set with Advice: The Impact of Graph Knowledge
cites work: Online Graph Exploration with Advice
cites work: On the Advice Complexity of Buffer Management
cites work: Online Computation with Advice
cites work: College Admissions and the Stability of Marriage
cites work: Q3579420
cites work: On Advice Complexity of the k-server Problem under Sparse Metrics
cites work: Information Complexity of Online Problems
cites work: Q4252706
cites work: Online bipartite matching with unknown distributions
cites work: On-line algorithms for weighted bipartite matching and stable marriages
cites work: Online bipartite matching with random arrivals
cites work: Online stochastic matching: online actions based on offline statistics
cites work: AdWords and generalized online matching
DOI: 10.1016/J.IPL.2014.06.013
description: scientific article; zbMATH DE number 6335103