Continuous Facility Location on Graphs

• Applicant: Professor Dr. Peter Rossmanith, since 6/2022
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 447534137

We consider continuous facility location problems on undirected graphs where all edges have unit length and where the facilities may be positioned on the vertices as well as on interior points of the edges. The goal is either to cover the entire graph with a minimum number of facilities with covering range \delta (covering version), or to place as many facilities as possible at pairwise distance at least \delta from each other (dispersion version).The goals in the project are to analyze the approximability and in-approximability of such facility location problems, to study their behavior in specially structured graph classes, and to investigate their computational complexity.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Professor Dr.-Ing. Gerhard Woeginger, until 6/2022