The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Blank, Lotte, Cabello, Sergio, Hajiaghayi, MohammadTaghi, Krauthgamer, Robert, Mahabadi, Sepideh, Nusser, André, Phillips, Jeff M., Sauer, Jonas
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

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

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
by: Mahabadi, Sepideh, et al.
Published: (2025)

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

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

Continual Counting with Gradual Privacy Expiration
by: Andersson, Joel Daniel, et al.
Published: (2024)

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

Single-Sample Bilateral Trade with a Broker
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2026)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

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

Moderate Dimension Reduction for $k$-Center Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2023)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

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

Composable Coresets for Constrained Determinant Maximization and Beyond
by: Mahabadi, Sepideh, et al.
Published: (2022)

Online Steiner Forest with Recourse
by: Long, Yaowei, et al.
Published: (2026)

Gains-from-Trade in Bilateral Trade with a Broker
by: Hajiaghayi, Ilya, et al.
Published: (2024)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Clustering Permutations: New Techniques with Streaming Applications
by: Chakraborty, Diptarka, et al.
Published: (2022)

Sequential Selection with Expirations
by: Xu, Yihua, et al.
Published: (2024)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
by: Krivošija, Amer, et al.
Published: (2025)

Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
by: Brânzei, Simina, et al.
Published: (2024)

Streaming Diameter of High-Dimensional Points
by: Halldórsson, Magnús M., et al.
Published: (2025)