Cover Image

Transposition is Nearly Optimal for IID List Update

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Coester, Christian
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Chasing Small Sets Optimally Against Adaptive Adversaries
by: Coester, Christian, et al.
Published: (2026)

Online Monotone Metric Embeddings
by: Coester, Christian, et al.
Published: (2026)

Randomized $k$-server in polynomial time
by: Coester, Christian, et al.
Published: (2026)

Smoothed Analysis of Online Metric Problems
by: Coester, Christian, et al.
Published: (2025)

Online 3-Taxi on General Metrics
by: Coester, Christian, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
by: Bai, Xingjian, et al.
Published: (2024)

List Update with Delays or Time Windows
by: Azar, Yossi, et al.
Published: (2023)

Learning-Augmented Priority Queues
by: Benomar, Ziyad, et al.
Published: (2024)

Online List Labeling with Near-Logarithmic Writes
by: Seybold, Martin P.
Published: (2024)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
by: Chhabra, Adil, et al.
Published: (2025)

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
by: Basiak, Mateusz, et al.
Published: (2025)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information
by: Siqueira, Gabriel, et al.
Published: (2025)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
by: Bishnu, Arijit, et al.
Published: (2024)

Nearly Optimal Internal Dictionary Matching
by: Chen, Jingbang, et al.
Published: (2023)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Near-Optimal Heaps and Dijkstra on Pointer Machines
by: van der Hoog, Ivor, et al.
Published: (2026)

Near-Optimal Property Testers for Pattern Matching
by: Jin, Ce, et al.
Published: (2025)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

Near-Optimal Dimension Reduction for Facility Location
by: Huang, Lingxiao, et al.
Published: (2024)

Nearly Optimal Bounds for Stochastic Online Sorting
by: Hu, Yang
Published: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Near-Optimal Four-Cycle Counting in Graph Streams
by: Lüderssen, Sebastian, et al.
Published: (2026)

A Near-Optimal Kernel for a Coloring Problem
by: Haviv, Ishay, et al.
Published: (2025)

Near Optimal Dual Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
by: Aamand, Anders, et al.
Published: (2024)

Deterministic $k$-Median Clustering in Near-Optimal Time
by: Costa, Martín, et al.
Published: (2025)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
by: Dughmi, Shaddin, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Near-Optimal Bayesian Online Assortment of Reusable Resources
by: Feng, Yiding, et al.
Published: (2025)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
by: Chen, Daoyuan, et al.
Published: (2024)

Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
by: De Marco, Gianluca, et al.
Published: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
by: Bhanja, Koustav, et al.
Published: (2025)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams
by: Ta, Hoang, et al.
Published: (2026)