Sublinear-time Algorithms
From MaRDI portal
Publication:4933363
DOI10.1007/978-3-642-16367-8_5zbMath1308.68064OpenAlexW1558964774MaRDI QIDQ4933363
Christian Sohler, Artur Czumaj
Publication date: 12 October 2010
Published in: Property Testing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_5
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Testing Lipschitz functions on hypergrid domains, Unnamed Item, Recognizing the tractability in big data computing, Detection of Long Edges on a Computational Budget: A Sublinear Approach
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal time bounds for approximate clustering
- A \(k\)-median algorithm with running time independent of data size
- Smaller coresets for \(k\)-median and \(k\)-means clustering
- Small space representations for metric min-sum \(k\)-clustering and their applications
- Quick approximation to matrices and applications
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Random sampling and approximation of MAX-CSPs
- A sublinear bipartiteness tester for bounded degree graphs
- Tolerant property testing and distance approximation
- Sublinear time algorithms for metric space problems
- Graph limits and parameter testing
- Property testing and its connection to learning and approximation
- Sublinear‐time approximation algorithms for clustering via random sampling
- Approximating average parameters of graphs
- Data Streams: Algorithms and Applications
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- On coresets for k-means and k-median clustering
- Better streaming algorithms for clustering problems
- Coresets in dynamic geometric data streams
- On k-Median clustering in high dimensions
- Every Monotone Graph Property Is Testable
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Testing of Clustering
- Local Search Heuristics for k-Median and Facility Location Problems
- Quick k-Median, k-Center, and Facility Location for Sparse Graphs
- An improved constant-time approximation algorithm for maximum~matchings
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Abstract Combinatorial Programs and Efficient Property Testers
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Fast monte-carlo algorithms for finding low-rank approximations
- Sublinear Geometric Algorithms
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Automata, Languages and Programming
- Automata, Languages and Programming
- Efficient testing of large graphs
- Property testing in bounded degree graphs
