Cover Image

Dynamic Metric Embedding into $\ell_p$ Space

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Banihashem, Kiarash, Hajiaghayi, MohammadTaghi, Kowalski, Dariusz R., Olkowski, Jan, Springer, Max
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

Beating Competitive Ratio 4 for Graphic Matroid Secretary
by: Banihashem, Kiarash, et al.
Published: (2025)

Online Sampling and Decision Making with Low Entropy
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2021)

Optimal Algorithms for Free Order Multiple-Choice Secretary
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2022)

Bi-Criteria Metric Distortion
by: Banihashem, Kiarash, et al.
Published: (2024)

A Dynamic Algorithm for Weighted Submodular Cover Problem
by: Banihashem, Kiarash, et al.
Published: (2024)

Matroid Algorithms Under Size-Sensitive Independence Oracles
by: Banihashem, Kiarash, et al.
Published: (2026)

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
by: Banihashem, Kiarash, et al.
Published: (2025)

Bandit Social Learning: Exploration under Myopic Behavior
by: Banihashem, Kiarash, et al.
Published: (2023)

Replicable Composition
by: Banihashem, Kiarash, et al.
Published: (2026)

Pandora with Inaccurate Priors
by: Banihashem, Kiarash, et al.
Published: (2025)

Active Learning for Decision Trees with Provable Guarantees
by: Moakhar, Arshia Soltani, et al.
Published: (2026)

Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
by: Hajiaghayi, Mohammad T., et al.
Published: (2024)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Fairness and Efficiency in Online Class Matching
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
by: Das, Debarati, et al.
Published: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)

2-Approximation for Prize-Collecting Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2023)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)

Prize-Collecting Forest with Submodular Penalties: Improved Approximation
by: Ahmadi, Ali, et al.
Published: (2025)

The Power of Recursive Embeddings for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2025)

Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
by: Kowalski, Dariusz R., et al.
Published: (2025)

Replication-proof Bandit Mechanism Design with Bayesian Agents
by: Shin, Suho, et al.
Published: (2023)

Optimal Contest Beyond Convexity
by: Golrezaei, Negin, et al.
Published: (2026)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
by: Blank, Lotte, et al.
Published: (2025)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2026)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Turnstile $\ell_p$ leverage score sampling with applications
by: Munteanu, Alexander, et al.
Published: (2024)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
by: Li, Yi, et al.
Published: (2022)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
by: Munteanu, Alexander, et al.
Published: (2024)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
by: Chiclana, Rafael, et al.
Published: (2025)

Towards Efficient Data Structures for Approximate Search with Range Queries
by: Kian, Ladan, et al.
Published: (2026)

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)

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

Iterative Refinement for $\ell_p$-norm Regression
by: Adil, Deeksha, et al.
Published: (2019)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
by: Davies, Sami, et al.
Published: (2025)