Cover Image

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bartal, Yair, Fandina, Ora N., Umboh, Seeun William
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online TCP Acknowledgment under General Delays
by: Bhore, Sujoy, et al.
Published: (2026)

Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
by: Shmoys, David, et al.
Published: (2026)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
by: Dinitz, Michael, et al.
Published: (2025)

Online Computation of String Net Frequency
by: Guo, Peaker, et al.
Published: (2024)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
by: Cervenjak, Philip, et al.
Published: (2024)

Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
by: Canonne, Clément L., et al.
Published: (2025)

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
by: Cervenjak, Philip, et al.
Published: (2026)

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
by: Ezra, Tomer, et al.
Published: (2024)

Colorful Vertex Recoloring of Bipartite Graphs
by: Patt-Shamir, Boaz, et al.
Published: (2025)

Optimal Dynamic Parameterized Subset Sampling
by: Gan, Junhao, et al.
Published: (2024)

Optimal bounds on a tree inference algorithm
by: Gardiner, Jack, et al.
Published: (2024)

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants
by: Banerjee, Sandip, et al.
Published: (2025)

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

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

Online Metric TSP
by: Bertram, Christian
Published: (2025)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
by: Räcke, Harald, et al.
Published: (2024)

A Subquadratic Bound for Online Bisection
by: Bienkowski, Marcin, et al.
Published: (2023)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
by: Kuszmaul, William, et al.
Published: (2025)

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

Dynamic Metric Embedding into $\ell_p$ Space
by: Banihashem, Kiarash, et al.
Published: (2024)

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
by: Li, Yingxi, et al.
Published: (2025)

Online Graph Embedding in Star Graphs
by: Dallot, Julien, et al.
Published: (2026)

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Nearly Tight Bounds for the Online Sorting Problem
by: Azar, Yossi, et al.
Published: (2025)

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

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
by: Kuszmaul, William
Published: (2025)

Bounding the Optimal Performance of Online Randomized Primal-Dual Methods
by: Xu, Pan
Published: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
by: Geng, Yutong, et al.
Published: (2025)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
by: Jeang, John, et al.
Published: (2026)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
by: Charikar, Moses, et al.
Published: (2023)

Hop-Constrained Metric Embeddings and their Applications
by: Filtser, Arnold
Published: (2021)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)