skip to content

Melanie Schmidt and her group work on the analysis, development and implementation of approximation algorithms for geometric data analysis. A current project is on clustering, in particular the theoretical analysis of practically relevant clustering objectives. This includes k-means clustering with and without various side constraints motivated by anonymity or fairness considerations or capacity restrictions.

The k-means objective asks for k centers such that the sum of squared distances of any point to its closest center is minimized.

Selected publications

  1. Dan Feldman, Melanie Schmidt, Christian Sohler: Turning Big Data into Tiny Data: Constant-size Coresets for k-means, PCA and Projective Clustering, 24. ACM-SIAM Symposium on Discrete Algorithms (SODA):1434-1453, 2013, and to appear at SIAM Journal of Computing.
  2. Anna Großwendt, Heiko Röglin, Melanie Schmidt: Analysis of Ward's method, 30. ACM-SIAM Symposium on Discrete Algorithms (SODA): 2939-2957, 2019.
  3. Hendrik Fichtenberger, Marc Gillé, Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler: BICO: BIRCH meets coresets for k-means clustering, 21. European Symposium on Algorithms (ESA): 481-492, 2013.
  4. Euiwoong Lee, Melanie Schmidt, John Wright: Improved and simplified inapproximability for k-means. Information Processing Letters 120: 40-43, 2017.
  5. Ioana Oriana Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, Melanie Schmidt: On the Cost of Essentially Fair Clusterings. APPROX-RANDOM 2019: 18:1-18:22.
  6. Anupam Gupta, Guru Guruganesh, Melanie Schmidt: Approximation Algorithms for Aversion k-Clustering via Local k-Median. 43. International Colloquium on Automata, Languages and Programming (ICALP): 66:1-66:13, 2016.
  7. Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, José Verschae: A Local-Search Algorithm for Steiner Forest. 9th Innovations in Theoretical Computer Science conference (ITCS): 31:1-31:17, 2018.
  8. Clemens Rösner, Melanie Schmidt: Privacy preserving clustering with constraints, 45. International Colloquium on Automata, Languages and Programming (ICALP): 96:1-96:14, 2018.
  9. Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler: Fair Coresets and Streaming Algorithms for Fair k-means. WAOA 2019: 232-251.
  10. Frank Hellweg, Melanie Schmidt, Christian Sohler: Testing Euclidean Spanners. 18. European Symposium on Algorithms (ESA): 60-71, 2010, also as a chapter in "Property Testing: Current Research and Surveys" (Editor: Oded Goldreich), 306-311, 2010.