Cover Image

Streaming Algorithms for Connectivity Augmentation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jin, Ce, Kapralov, Michael, Mahabadi, Sepideh, Vakilian, Ali
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

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

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

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

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
by: Dong, Yinhao, et al.
Published: (2024)

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

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

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

On the Streaming Complexity of Expander Decomposition
by: Chen, Yu, et al.
Published: (2024)

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

New and Improved Bounds for Markov Paging
by: Pabbaraju, Chirag, et al.
Published: (2025)

Graph-Based Algorithms for Diverse Similarity Search
by: Anand, Piyush, et al.
Published: (2025)

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

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
by: Kapralov, Michael, et al.
Published: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

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

Engineering Weighted Connectivity Augmentation Algorithms
by: Faraj, Marcelo Fonseca, et al.
Published: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

Spectral Clustering in Birthday Paradox Time
by: Kapralov, Michael, et al.
Published: (2026)

Recovering Communities in Structured Random Graphs
by: Kapralov, Michael, et al.
Published: (2026)

Scalable Algorithms for Individual Preference Stable Clustering
by: Mosenzon, Ron, et al.
Published: (2024)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

Memory Reallocation with Polylogarithmic Overhead
by: Jin, Ce
Published: (2026)

Learning-Based Algorithms for Graph Searching Problems
by: DePavia, Adela Frances, et al.
Published: (2024)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

Streaming Attention Approximation via Discrepancy Theory
by: Kochetkova, Ekaterina, et al.
Published: (2025)

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

Sublinear Time Low-Rank Approximation of Hankel Matrices
by: Kapralov, Michael, et al.
Published: (2025)

Efficiently Computing Similarities to Private Datasets
by: Backurs, Arturs, et al.
Published: (2024)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
by: Kapralov, Michael, et al.
Published: (2022)

Learning-Augmented Streaming Algorithms for Correlation Clustering
by: Dong, Yinhao, et al.
Published: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

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

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

Spectral Clustering with Side Information
by: Fichtenberger, Hendrik, et al.
Published: (2025)