A2 Algorithmic aspects of learning methods in embedded systems

Prof. Dr. Jan Vahrenhold

Prof. Dr. Christian Sohler

In this project we will investigate algorithmic foundations of learning methods in ressource-constrained embedded systems. To model such systems, we will focus not only on standard complexity measures such as running time and space complexity but plan to consider also measures specific to embedded systems such as energy consumption or bandwidth. If applicable, our analyses shall aim at giving guarantees with respect to the quality of the computed solution. Ultimately, we hope to obtain general paradigms for designing efficient algorithm in ressource-constrained embedded systems.

Publications

• [1] Ackermann, M. R., J. Blömer und C. Sohler:
  Clustering for metric and non-metric distance measures. In: Teng, S.-H. (Hrsg.): Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, S. 799 - 808, 2008.
• [2] Arge, L. A., K. H. Hinrichs, J. Vahrenhold und J. S. Vitter:
  Efficient Bulk Operations on Dynamic R-trees. Algorithmica, 33(1):104 - 128, März 2002.
• [3] Blunck, H. und J. Vahrenhold:
  In-Place Randomized Slope Selection. In: Proceedings of the 6th International Conference on Algorithms and Complexity, Bd. 3998 d. Reihe Lecture Notes in Computer Science, S. 31 - 40, Berlin, 2006. Springer.
• [4] Blunck, H. und J. Vahrenhold:
  In-Place Algorithms for Computing (Layers of) Maxima. Algorithmica, 57(1):1 - 21, Mai 2010.
• [5] Bose, P., A. Maheshwari, P. Morin, J. Morrison, M. Smid und J. Vahrenhold:
  Space-Efficient Geometric Divide-and-Conquer Algorithms. Computational Geometry: Theory & Applications., 37(3):209 - 227, Aug. 2007.
• [6] Feldman, D., M. Monemizadeh, C. Sohler und D. Woodruff:
  Coresets and Sketches for High Dimensional Subspace Approximation Problems. In: Proceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms, S. 630 - 649, 2010.
• [7] Frahling, G., P. Indyk und C. Sohler:
  Sampling in Dynamic Data Streams and Applications. International Journal on Computational Geometry and Applications, 18(1/2):3 - 28, 2008.
• [8] Frahling, G. und C. Sohler:
  Coresets in dynamic geometric data streams. In: Gabow, H. N. und R. Fagin (Hrsg.): Proceedings of the 37th Annual ACM Symposium on Theory of Computing, S. 209 - 217, 2005.
• [9] Frahling, G. und C. Sohler:
  A Fast k-Means Implementation Using Coresets. International Journal on Computational Geometry and Applications, 18(6):605 - 625, 2008.
• [10] Gehweiler, J., C. Lammersen und C. Sohler:
  A distributed O(1)- approximation algorithm for the uniform facility location problem. In: Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures, S. 237 - 243, 2006.
• [11] Gieseke, F., J. Gudmundsson und J. Vahrenhold:
  Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies. Journal of Discrete Algorithms, 8(3):259 - 272, Sep. 2010. http://dx.doi.org/10.1016/j.jda.2010.03.001.
• [12] Hazel, T., L. Toma, J. Vahrenhold und R. Wickremesinghe:
  TerraCost: A Versatile and Scalable Approach to Computing Least-Cost-Path Surfaces for Massive Grid-Based Terrains. ACM Journal of Experimental Algorithmics, 12, Juni 2008. Article 1.9, 31 pages.

Publications (state of the art)

• [78] Vahrenhold, J.:
  An In-Place Algorithm for Klee’s Measure Problem in Two Dimensions. Information Processing Letters, 102(4):169–174, Mai 2007.
• [79] Vahrenhold, J.:
  Line-Segment Intersection Made In-Place. Computational Geometry: Theory & Applications, 38(3):213–230, Okt. 2007.