Hauptinhalt
Project "Sublinear Time Algorithms"
[
Members] [
Support] [
Overview]
[
Results]
Support
Research supported by Deutsche Forschungsgemeinschaft, grant SO 514/3-1.
The development of efficient algorithms for analyzing large data sets has become a central topic in many applications of computer science: In many cases it is not even possible to completely store the input data of an algorithm completely on a hard disk due to its size, not to speak about storing it in the main memory for processing. In such cases, depending on environmental aspects, even linear time algorithms may be to slow for solving the problem efficiently enough. A feasible method for extracting relevant information out of the data may then be to work with random samples: Similarly to a survey, one tries to chose a sample cleverly to get a good representation of the overall data while on the other hand trying to minimize the sample size. Since an algorithm that uses this technique only looks at a small fraction of the data, we call such algorithms
Sublinear Time Algorithms.
The aim of this project is the further development of techniques to for sublinear time algorithms. For this purpose, we concentrate on
Property Testing and
Sublinear Approximation Algorithms in
sparse and
geometric graphs for developing new algorithms for specific problems and new methods for the sampling procedure and its analysis; we will place particular emphasis on exemplary problems like
Matching,
Independent Sets,
Vertex Cover or
Travelling Salesperson. Additionally, we will try to find classes of problems for which one can give sublinear approximation algorithms.
Testing Euclidean Spanners
For many types of graphs (for example traffic and supply networks), it is a natural question to ask whether paths between two arbitrary vertices are short. A spanner is a graph in which this holds for every pair of vertices: We say that a geometric graph G=(V,E) is called a euclidean (1+δ)-spanner, if for each pair v and w of vertices the shortest path between v and w using edges of G is at most 1+δ times longer than the euclidean distance between v and w. Of course, having this property is desirable for the aforementioned types of graphs.
We develop a property testing algorithm that can test whether a given bounded-degree geometric graph is a euclidean (1+δ)-spanner with a query complexity of Õ(sqrt(n)/poly(δ, ε)).
Frank Hellweg,
Melanie Schmidt and Christian Sohler:
Testing Euclidean Spanners. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA), 2010
Letzte Änderung am 16.05.2011 von F. Hellweg
