scientific article; zbMATH DE number 7236471

DOI10.4230/LIPICS.SOCG.2018.67MaRDI QIDQ5116527zbMATH OpenFDO

Authors Sharath Raghvendra

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1803.07206

zbMATH Keywords

adversarial modelbipartite matchingline metriconline algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• An optimal deterministic algorithm for online \(b\)-matching
• Approximation and Online Algorithms
• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A polyhedral approach to online bipartite matching
• A Polyhedral Approach to Online Bipartite Matching
• Near optimal algorithms for online maximum weighted b-matching

Cites work

• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A robust and optimal online algorithm for minimum metric bipartite matching
• Approximation and Online Algorithms
• Competitive algorithms for server problems
• On the k -server conjecture
• On-line algorithms for weighted bipartite matching and stable marriages
• Online Weighted Matching
• The Online Metric Matching Problem for Doubling Metrics

Cited in

(33)

• Online matching on a line
• A poly-log competitive posted-price algorithm for online metrical matching on a spider
• Online bottleneck semi-matching
• Online scheduling of car-sharing request pairs between two locations
• Greedy metric minimum online matchings with random arrivals
• A collection of lower bounds for online matching on the line
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• Online minimum matching with uniform metric and random arrivals
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• A robust and optimal online algorithm for minimum metric bipartite matching
• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• Competitive analysis for two variants of online metric matching problem
• Stochastic online metric matching
• Approximation and Online Algorithms
• Online request server matching
• 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 Metric Algorithms with Untrusted Predictions
• 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
• Online facility assignment for general layout of servers on a line
• Capacity-insensitive algorithms for online facility assignment problems on a line
• Improved online sorting
• Online deterministic minimum cost bipartite matching with delays on a line
• Online deterministic minimum cost bipartite matching with delays on a line
• Online metric matching on the line with recourse
• Matching on the line admits no \(o(\sqrt{\log n})\)-competitive algorithm
• Online sorting and online TSP: Randomized, stochastic, and high-dimensional
• Stochastic online metric matching: adversarial is no harder than stochastic
• Geometric bipartite matching based exact algorithms for server problems
• \textsc{Permutation} for online metric matching with \(m\) distinct servers
• A nearly optimal deterministic algorithm for online transportation problem

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116527)