Sublinear-time Algorithms (Q4933363)

scientific article; zbMATH DE number 5799052

Language	Label	Description	Also known as
English	Sublinear-time Algorithms	scientific article; zbMATH DE number 5799052

Statements

instance of

scholarly article

0 references

title

Sublinear-time Algorithms (English)

0 references

0 references

0 references

0 references

12 October 2010

0 references

zbMATH Keywords

sublinear time algorithms

0 references

sublinear approximation algorithms

0 references

survey paper

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-642-16367-8_5

0 references

cites work

Testing of Clustering

0 references

Random sampling and approximation of MAX-CSPs

0 references

Efficient testing of large graphs

0 references

A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

0 references

Every Monotone Graph Property Is Testable

0 references

A Characterization of the (Natural) Graph Properties Testable with One-Sided Error

0 references

Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems

0 references

Local Search Heuristics for k-Median and Facility Location Problems

0 references

Automata, Languages and Programming

0 references

Q3549723

0 references

Graph limits and parameter testing

0 references

Better streaming algorithms for clustering problems

0 references

Sublinear Geometric Algorithms

0 references

Approximating the Minimum Spanning Tree Weight in Sublinear Time

0 references

On k-Median clustering in high dimensions

0 references

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

0 references

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

0 references

Q4796180

0 references

Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time

0 references

Sublinear‐time approximation algorithms for clustering via random sampling

0 references

Abstract Combinatorial Programs and Efficient Property Testers

0 references

Small space representations for metric min-sum \(k\)-clustering and their applications

0 references

Q2753932

0 references

On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph

0 references

Q3152421

0 references

Coresets in dynamic geometric data streams

0 references

Quick approximation to matrices and applications

0 references

Fast monte-carlo algorithms for finding low-rank approximations

0 references

Q4224925

0 references

Property testing and its connection to learning and approximation

0 references

Property testing in bounded degree graphs

0 references

A sublinear bipartiteness tester for bounded degree graphs

0 references

Approximating average parameters of graphs

0 references

On coresets for k-means and k-median clustering

0 references

Smaller coresets for \(k\)-median and \(k\)-means clustering

0 references

Sublinear time algorithms for metric space problems

0 references

Automata, Languages and Programming

0 references

Optimal time bounds for approximate clustering

0 references

A \(k\)-median algorithm with running time independent of data size

0 references

Q2768331

0 references

Data Streams: Algorithms and Applications

0 references

Tolerant property testing and distance approximation

0 references

Q4788610

0 references

Quick k-Median, k-Center, and Facility Location for Sparse Graphs

0 references

An improved constant-time approximation algorithm for maximum~matchings

0 references

Identifiers

zbMATH Open document ID

1308.68064

0 references

DOI

10.1007/978-3-642-16367-8_5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4933363