Cover Image

Online Monotone Metric Embeddings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Coester, Christian, Huang, Yichen
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

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)

Transposition is Nearly Optimal for IID List Update
by: Coester, Christian
Published: (2026)

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

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

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

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

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

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
by: Bartal, Yair, et al.
Published: (2024)

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)

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
by: Kuhnle, Alan
Published: (2026)

Monotone Submodular Multiway Partition
by: Bi, Richard, et al.
Published: (2024)

Testing Monotonicity of Real-Valued Functions on DAGs
by: Yoshida, Yuichi
Published: (2026)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

Exploring Monotone Priority Queues for Dijkstra Optimization
by: Costa, Jonas, 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)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
by: Kosolobov, Dmitry
Published: (2024)

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
by: Pinto Jr, Renato Ferreira
Published: (2024)

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

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
by: Dürr, Anita
Published: (2022)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
by: Kaul, Matthias, et al.
Published: (2025)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
by: Fang, Qiangpeng, et al.
Published: (2026)

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
by: Jansen, Klaus, et al.
Published: (2026)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
by: Black, Hadley
Published: (2023)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
by: Beines, Arne, et al.
Published: (2024)

Parsimonious Learning-Augmented Online Metric Matching
by: Shin, Yongho, et al.
Published: (2026)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
by: Kobayashi, Yasuaki, et al.
Published: (2020)

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

Clustering in Varying Metrics
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
by: Black, Hadley, et al.
Published: (2023)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

Highway Dimension: a Metric View
by: Feldmann, Andreas Emil, et al.
Published: (2024)

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

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
by: Nikolov, Aleksandar, et al.
Published: (2026)