Sublinear-time Algorithms
From MaRDI portal
Cites work
- A \(k\)-median algorithm with running time independent of data size
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- A sublinear bipartiteness tester for bounded degree graphs
- Abstract Combinatorial Programs and Efficient Property Testers
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating average parameters of graphs
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Automata, Languages and Programming
- Automata, Languages and Programming
- Better streaming algorithms for clustering problems
- Coresets in dynamic geometric data streams
- Data Streams: Algorithms and Applications
- Efficient testing of large graphs
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Every Monotone Graph Property Is Testable
- Fast monte-carlo algorithms for finding low-rank approximations
- Graph limits and parameter testing
- scientific article; zbMATH DE number 1670655 (Why is no real title available?)
- scientific article; zbMATH DE number 1819631 (Why is no real title available?)
- scientific article; zbMATH DE number 5485551 (Why is no real title available?)
- scientific article; zbMATH DE number 1241385 (Why is no real title available?)
- scientific article; zbMATH DE number 1857651 (Why is no real title available?)
- scientific article; zbMATH DE number 1875421 (Why is no real title available?)
- Local Search Heuristics for k-Median and Facility Location Problems
- On k-Median clustering in high dimensions
- On coresets for k-means and k-median clustering
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Optimal time bounds for approximate clustering
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Property testing and its connection to learning and approximation
- Property testing in bounded degree graphs
- Quick k-Median, k-Center, and Facility Location for Sparse Graphs
- Quick approximation to matrices and applications
- Random sampling and approximation of MAX-CSPs
- Small space representations for metric min-sum k-clustering and their applications
- Smaller coresets for k-median and k-means clustering
- Sublinear Geometric Algorithms
- Sublinear time algorithms for metric space problems
- Sublinear time approximate clustering
- Sublinear‐time approximation algorithms for clustering via random sampling
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Testing of Clustering
- Tolerant property testing and distance approximation
Cited in
(10)- Testing Lipschitz functions on hypergrid domains
- Subexponential parameterized algorithms
- Sublinear Computation Paradigm
- Detection of long edges on a computational budget: A sublinear approach
- scientific article; zbMATH DE number 5057523 (Why is no real title available?)
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- scientific article; zbMATH DE number 7651177 (Why is no real title available?)
- Sublinear algorithms for scheduling with chain precedence constraints
- Range counting oracles for geometric problems
- Quantum property testing in sparse directed graphs
This page was built for publication: Sublinear-time Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933363)
