We offer a full-time PhD position (German salary level TVöD Bund E 13) at the Algorithms and Complexity Department at the Max Planck Institute for Informatics (MPI-INF) in Saarbrücken, Germany. The starting date is negotiable and could be as early as June, 2022. The position will be for three years with the possibility of extension.

You will be part of a research project on Approximation Algorithms for Combinatorial Optimization Problems with Packing Constraints, which is funded by the DFG (German Research Foundation). You will design and analyze algorithms for problems arising in clustering, submodular optimization, network design, and geometric optimization. Moreover, you will identify the limits of the algorithmic solvability of these problems, in particular, the hardness of approximation. See below for a list of project-relevant papers. You will be co-supervised by Prof. Danupon Nanongkai and myself. I am the principal investigator of the project.

You hold a master's degree (ideally) or a bachelor's degree in computer science, mathematics (or a related field) and have an excellent academic record. You are enthusiastic about theoretical and mathematical foundations of computer science and have a solid background in this regard. You are highly self-motivated, excited to work independently on hard problems, to learn new techniques, but also to discuss ideas with your supervisors or in a team with other researchers. Please check the regulations for starting a PhD.

We, the Algorithms and Complexity Department headed by Prof. Danupon Nanongkai, are a strong, vibrant, broadly interested, and internationally highly renowned group of researchers. We are part of one of the strongest research clusters for algorithms and complexity in Europe. We closely collaborate with researchers in other institutes on the campus, including the Department of Computer Science of Saarland University, CISPA Helmholtz Center for Information Security, and Max Planck Institute for Software Systems.

Our institute, MPI-INF, is among the more than 80 institutes run by the Max Planck Society. The MPIs are Germany’s premier basic research institutes performing world-class, basic research in the fields of medicine, biology, chemistry, physics, technology, and the humanities. Since 1948, MPI researchers have been awarded 21 Nobel prizes certifying the excellence of the research at MPIs.

The Max Planck Society seeks to increase the number of women in those areas where they are underrepresented and therefore explicitly encourages women to apply. The Max Planck Society is further committed to employing more individuals with handicaps and particularly encourages these to apply.

Please send your application to my email address. Include a short letter of motivation (about one page), a CV, names of two references, as well as electronic copies of your degree certificates, all as a single PDF.

Please do not hesitate to contact me in case of questions. I start reviewing the applications as of April, 15 and proceed with the selection process. However, feel free to send me your application afterwards.

Project-Relevant Papers

To give you an impression of the topics and algorithmic/mathematical tools relevant to the project, please find below an (incomplete) list of related papers.

• Constant-Factor Approximation for Ordered k-Median (preprint)
  Jarosław Byrka, Krzysztof Sornat, Joachim Spoerhase
  Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC’18)
• Constant Approximation for Capacitated k-Median with (1+eps)-Capacity Violation (preprint)
  Gökalp Demirci, Shi Li
  Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16)
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems (preprint)
  Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki, Joachim Spoerhase
  Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA’15)
• LP-Based Algorithms for Capacitated Facility Location (journal version)
  Hyung-Chan An, Mohit Singh, and Ola Svensson
  SIAM Journal on Computing (2017)
  Preliminary version at FOCS'14
• Tight FPT Approximations for k-Median and k-Means (conference proceedings)
  Vincent Cohen-Addad, Jason Li
  Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP'19)
• A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints (preprint)
  Eyal Mizrachi,Roy Schwartz, Joachim Spoerhase, and Sumedha Uniyal
  Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP'19)
• A Threshold of ln n for Approximating Set Cover (journal version)
  Uriel Feige
  Journal of the ACM (1998)
  Proc. 28th Annual ACM Symposium on the Theory of Computing (STOC'96)
• On LP-Based Approximability for Strict CSPs (conference proceedings)
  Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi
  Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'11)