A o(n)-competitive deterministic algorithm for online matching on a line
From MaRDI portal
(Redirected from Publication:2415368)
A \(o(n)\)-competitive deterministic algorithm for online matching on a line
A \(o(n)\)-competitive deterministic algorithm for online matching on a line
Recommendations
Cites work
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- A collection of lower bounds for online matching on the line
- A randomized O(^2k)-competitive algorithm for metric bipartite matching
- A robust and optimal online algorithm for minimum metric bipartite matching
- A tight bound on approximating arbitrary metrics by tree metrics
- Approximation and Online Algorithms
- scientific article; zbMATH DE number 7236471 (Why is no real title available?)
- On a Greedy Heuristic for Complete Matching
- On the k -server conjecture
- On-line algorithms for weighted bipartite matching and stable marriages
- Online matching on a line
- Online Weighted Matching
- Randomized online algorithms for minimum metric bipartite matching
- Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
- Searching in the plane
- The Online Metric Matching Problem for Doubling Metrics
- The Online Transportation Problem
- The Online Transportation Problem: On the Exponential Boost of One Extra Server
Cited in
(18)- An optimal deterministic algorithm for online \(b\)-matching
- Online matching on a line
- Online bottleneck semi-matching
- A collection of lower bounds for online matching on the line
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- scientific article; zbMATH DE number 7236471 (Why is no real title available?)
- Approximation and Online Algorithms
- Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
- scientific article; zbMATH DE number 7758339 (Why is no real title available?)
- Online bottleneck matching on a line
- Online semi-matching problem with two heterogeneous sensors in a metric space
- Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
- Deterministic primal-dual algorithms for online k-way matching with delays
- Deterministic primal-dual algorithms for online \(k\)-way matching with delays
- Online deterministic minimum cost bipartite matching with delays on a line
- On the advice complexity of online matching on the line
- Matching on the line admits no \(o(\sqrt{\log n})\)-competitive algorithm
- Stochastic online metric matching: adversarial is no harder than stochastic
This page was built for publication: A \(o(n)\)-competitive deterministic algorithm for online matching on a line
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415368)
