Image de couverture de livre

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Dufay, Marc, Wattenhofer, Roger
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
par: Kalavas, Andreas, et autres
Publié: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
par: Kalavas, Andreas, et autres
Publié: (2025)

On Thin Perfect Matchings up to Polylogarithmic Factors
par: Haqi, Alireza, et autres
Publié: (2026)

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
par: Kuo, Tung-Wei
Publié: (2024)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
par: Chuzhoy, Julia, et autres
Publié: (2026)

Memory Reallocation with Polylogarithmic Overhead
par: Jin, Ce
Publié: (2026)

Polylogarithmic Approximation for Robust s-t Path
par: Li, Shi, et autres
Publié: (2023)

Dynamic Longest Common Substring in Polylogarithmic Time
par: Charalampopoulos, Panagiotis, et autres
Publié: (2020)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
par: Chekuri, Chandra, et autres
Publié: (2024)

Perfect $L_p$ Sampling with Polylogarithmic Update Time
par: Swartworth, William, et autres
Publié: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
par: Bernstein, Aaron, et autres
Publié: (2025)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
par: Jiang, Yonggang, et autres
Publié: (2025)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
par: Agarwal, Arpit, et autres
Publié: (2024)

Online Matching with Delays and Size-based Costs
par: Kawase, Yasushi, et autres
Publié: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
par: Anand, Aditya, et autres
Publié: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
par: Koh, Zhuan Khye, et autres
Publié: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
par: Hua, Kevin, et autres
Publié: (2024)

When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching
par: Udwani, Rajan
Publié: (2023)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
par: Wan, Zongqi, et autres
Publié: (2024)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
par: Tian, Kangyi, et autres
Publié: (2026)

A Competitive Algorithm for Throughput Maximization on Identical Machines
par: Moseley, Benjamin, et autres
Publié: (2021)

Tight Competitive and Variance Analyses of Matching Policies in Gig Platforms
par: Xu, Pan
Publié: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
par: Bucić, Matija, et autres
Publié: (2025)

Competitive Online Transportation Simplified
par: Arndt, Stephen, et autres
Publié: (2025)

A Faster Deterministic Approximation Algorithm for TTP-2
par: Kanaya, Yuga, et autres
Publié: (2023)

Weighted $k$-Server Admits an Exponentially Competitive Algorithm
par: Bijoy, Adithya, et autres
Publié: (2025)

Semi-Streaming Algorithms for Hypergraph Matching
par: Reinstädtler, Henrik, et autres
Publié: (2025)

Engineering Hypergraph $b$-Matching Algorithms
par: Großmann, Ernestine, et autres
Publié: (2024)

Algorithms for Parameterized String Matching with Mismatches
par: Saha, Apurba, et autres
Publié: (2024)

Efficient Parallel Algorithms for Hypergraph Matching
par: Reinstädtler, Henrik, et autres
Publié: (2026)

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
par: Basiak, Mateusz, et autres
Publié: (2025)

Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
par: Lebeda, Christian Janos, et autres
Publié: (2024)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
par: Gomes, Guilherme C. M., et autres
Publié: (2024)

Efficient Kernelization Algorithm for Bipartite Graph Matching
par: Wu, Guang, et autres
Publié: (2024)

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
par: Derakhshan, Mahsa, et autres
Publié: (2026)

Online Matching under KIID: Enhanced Competitive Analysis through Ordinary Differential Equation Systems
par: Xu, Pan
Publié: (2025)

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
par: Xu, Haoran, et autres
Publié: (2026)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
par: Fischer, Manuela, et autres
Publié: (2021)