Sample and Expand: Discovering Low-rank Submatrices With Quality Guarantees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ciaperoni, Martino, Gionis, Aristides, Mannila, Heikki
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

Sequential Diversification with Provable Guarantees
by: Wang, Honglian, et al.
Published: (2024)

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
by: Zhang, Guangyi, et al.
Published: (2025)

Efficient and Adaptive Estimation of Local Triadic Coefficients
by: Sarpe, Ilie, et al.
Published: (2025)

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information
by: Gadekar, Ameet, et al.
Published: (2025)

OptiRefine: Densest subgraphs and maximum cuts with $k$ refinements
by: Tu, Sijing, et al.
Published: (2025)

Label-consistent clustering for evolving data
by: Gadekar, Ameet, et al.
Published: (2025)

Scalable Temporal Motif Densest Subnetwork Discovery
by: Sarpe, Ilie, et al.
Published: (2024)

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
by: Zhang, Guangyi, et al.
Published: (2026)

Streaming Stochastic Submodular Maximization with On-Demand User Requests
by: Wang, Honglian, et al.
Published: (2026)

Khatri-Rao Clustering for Data Summarization
by: Ciaperoni, Martino, et al.
Published: (2026)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
by: Thejaswi, Suhas, et al.
Published: (2024)

Restless reachability problems in temporal graphs
by: Thejaswi, Suhas, et al.
Published: (2020)

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

Latency Guarantees for Caching with Delayed Hits
by: Gurushankar, Keerthana, et al.
Published: (2025)

Local Centrality Minimization with Quality Guarantees
by: Miyauchi, Atsushi, et al.
Published: (2024)

New Approximation Guarantees for The Inventory Staggering Problem
by: Alon, Noga, et al.
Published: (2025)

Node ranking in labeled networks
by: Arachchi, Chamalee Wickrama, et al.
Published: (2025)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
by: Zhao, Jingyang, et al.
Published: (2023)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
by: Ahmed, Reyan, et al.
Published: (2024)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
by: Ghaffari, Mohsen, et al.
Published: (2025)

Fast Construction of Partitioned Learned Bloom Filter with Theoretical Guarantees
by: Sato, Atsuki, et al.
Published: (2024)

Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks
by: Chen, Chi-Yeh
Published: (2025)

Approximating Single-Source Personalized PageRank with Absolute Error Guarantees
by: Wei, Zhewei, et al.
Published: (2024)

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
by: Gutin, Gregory, et al.
Published: (2022)

Distributed Freeze Tag: a Sustainable Solution to Discover and Wake-up a Robot Swarm
by: Gavoille, Cyril, et al.
Published: (2025)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
by: Brinkop, Hauke, et al.
Published: (2025)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
by: Grilnberger, Mara, et al.
Published: (2026)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
by: Bai, Yuhang, et al.
Published: (2026)

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

On the Adversarial Robustness of Online Importance Sampling
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Dimension-Free Correlated Sampling for the Hypersimplex
by: Joseph, et al.
Published: (2025)

Fast Sampling Based Sketches for Tensors
by: Swartworth, William, et al.
Published: (2024)

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

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

Low Sensitivity Hopsets
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Spectral Guarantees for Adversarial Streaming PCA
by: Price, Eric, et al.
Published: (2024)

Optimal Phylogenetic Reconstruction from Sampled Quartets
by: Arvanitakis, Dionysis, et al.
Published: (2026)

Efficient Computation of Periods and Covers Using Sampling
by: Lecroq, Thierry, et al.
Published: (2024)

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)