Research supported by Deutsche Forschungsgemeinschaft, grants SO 514/3-1 and SO 514/3-2.
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.