Prof. Dr. Sándor Fekete

Technische Universität Braunschweig
Institute of Operating Systems and Computer Networks (IBR)
Mühlenpfordstr. 23
D-38106 Braunschweig
Phone: +49 531 391 3110
E-Mail: s.fekete@tu-braunschweig.de
Website: www.ibr.cs.tu-bs.de

Researcher’s Career

  • Head of Algorithms Group at Institute of Operating Systems and Computer Networks, TU Braunschweig
  • Professor for Computer Science, TU Braunschweig
  • Associate Professor for Mathematics, TU Braunschweig
  • Associate Professor for Mathematics, TU Berlin
  • Scientific Assistant at the Center for Parallel Computing, University of Cologne
  • Postdoc at Stony Brook University, USA
  • Ph.D. at the University of Waterloo, Canada, Department of Combinatorics and Optimization
  • Studies of Mathematics and Physics, University of Cologne

Mission Statement

Algorithms and optimization are the core of our modern digital world. Our work combines state-of-the-art fundamental research in theoretical computer science with a wide range of interdiscipinary cooperations with areas such as robotics, distributed systems, electrical engineering, traffic
management, biology and economics.

Research

Computational geometry: Our group has grown into one of the leading German centers for computational geometry, a branch of computer science devoted to the study of algorithms dealing with geometry. This includes problems arising from explicitly geometric settings, such as motion planning, geographic information systems, or computer graphics. Our specialty are approximation algorithms for NP-hard geometric problems, as well as exact methods.

Robot navigation: An algorithmic application area with particularly strong interaction between theory and practice arises from exploring, searching or mapping of a geometric region by one or many autonomous devices. We have developed a range of new algorithmic approaches for a wide spectrum of challenges.

Graph algorithms: Many optimization problems can be formulated in a discrete setting, often by generalizing geometric problems to more abstract scenarios. On the other hand, discretizing continuous geometric setups often leads to a simplified problem. We have made a number of significant contributions to the relationship between geometric and graph problems, in particular to the theory of algorithmic complexity.

Distributed algorithms: While traditional algorithms consider single processors, many new challenges in our modern world arise from combining the local information and local actions of many processors. We continue to make contributions to many related areas, e.g., to distributed
sensor networks, which combine the limited capabilities of numerous sensors and actors.

Algorithmics of self-organization: Dealing with many small collaborating agents ultimately leads to the algorithmic theory of programmable matter. We have made a number of contributions to the theory of tile self-assembly, which is based on using DNA as building material. Other recent work considers programming huge particle swarms.

Game theory: How can we understand and improve collaboration between selfish agents? This is a recent research area.

credits: IBR

Selected Publications

  • S.K. Lee, S.P. Fekete and J. McLurkin: Strctured Triangulation in Multi-Robot Systems: Coverage, Patrolling, Voronoi Partitions, and Geodesic Centers, International Journal of Robotics Research, 35, 10, pp. 1234-1260, 2016.
  • S.P. Fekete, J. Hendricks, M. J. Patitz, T. Rogers, and R. T. Schweller: Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly, Proceedings of the Twenty-Sixth Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 148-167, 2015.
  • E.D. Demaine, M.L. Demaine, S.P. Fekete, M. J. Patitz, R. T. Schweller, A. Winslow, and D. Woods: One Tile to Rule Them All: Simulating any Turing machine, tile assembly system, or tiling system with one puzzle piece, Automata, Languages, and Programming – 41st International Colloquium (ICALP), pp. 368-379, 2014.
  • G. Coulson, B. Porter, I. Chatzigiannakis, C. Koninis, S. Fischer, D. Pfisterer, D. Bimschas, T. Braun, P. Hurni, M. Anwander, G. Wagenknecht, S.P. Fekete, A. Kröller, and T. Baumgartner: Flexible experimentation in wireless sensor networks. Communications of the ACM 55, 1, pp. 82-90, 2012.
  • A. Kröller, T. Baumgartner, S.P. Fekete, and C Schmidt: Exact solutions and bounds for general art gallery problems, Journal of Experimental Algorithmics (JEA), 17, 2.3, 2012.
  • S.P. Fekete, C. Schmidt, A. Wegener, H. Hellbrück, and S. Fischer: Empowered by wireless communication: Distributed methods for self-organizing traffic collectives, ACM Transactions on Autonomous and Adaptive Systems, 5, 3, pp. 11:1-30, 2010.