Advice complexity of online non-crossing matching
From MaRDI portal
Publication:2678256
DOI10.1016/j.comgeo.2022.101943OpenAlexW4294631421WikidataQ114195403 ScholiaQ114195403MaRDI QIDQ2678256
Denis Pankratov, A. M. Lavasani
Publication date: 9 January 2023
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2112.08295
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Online algorithms; streaming algorithms (68W27)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On the advice complexity of online bipartite matching and online stable marriage
- Non-crossing matchings of points with geometric objects
- The string guessing problem as a method to prove lower bounds on the advice complexity
- A matching problem in the plane
- On a matching problem in the plane
- Discrete geometry on colored point sets in the plane -- a survey
- Bayesian Mechanism Design
- Online Stochastic Matching: Online Actions Based on Offline Statistics
- On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
- Online Stochastic Weighted Matching: Improved Approximation Algorithms
- Linear-Time Approximation for Maximum Weight Matching
- Improved Bounds for Online Stochastic Matching
- The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
- Efficient breakout routing in printed circuit boards
- Online Stochastic Matching: Beating 1-1/e
- Online Stochastic Matching: New Algorithms with Better Bounds
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
- On conceptually simple algorithms for variants of online bipartite matching
This page was built for publication: Advice complexity of online non-crossing matching
