Home
Hasso-Plattner-Institut
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

schließen

schließen

schließen

schließen

schließen

schließen

schließen

schließen
  1. esa-random-sagt

10.07.2023

Three Papers accepted at ESA, RANDOM and SAGT

We are proud to announce three recently accepted papers by group members at ESA, RANDOM and SAGT! For the European Symposium on Algorithms (ESA) the paper On the Giant Component of Geometric Inhomogeneous Random Graphs was accepted in Track S, which focuses on simplicity. It was written by Janosch Ruff and Ziena Zeif in collaboration with researchers at the Karlsruhe Institute of Technology. Geometric Inhomogeneous Random Graphs are of interest due to their structural properties similar to those of real-wold networks when it comes to the performance of graph algorithms. A fundamental question for random graphs is the question when there exists with high probability a Giant component (a connected component of size linear in the number of vertices). In the paper, the authors provide a very simple proof of this fundamental result and also discuss implications of the technique to other connected components that emerge in Geometric Inhomogeneous Random Graphs.

The second paper Perfect Sampling for Hard Spheres from Strong Spatial Mixing was accepted at the International Conference on Randomization and Computation (RANDOM) and was written by Marcus Pappik and Andreas Göbel with researchers at the Georgia Institute of Technology. The authors provide a perfect sampling algorithm for the finite-volume hard-sphere model, a well-known model for gases and liquids of interacting particles from statistical physics. Their algorithm yields an expected running time linear in the volume of the considered region whenever the model exhibits a sufficiently strong decay of correlations between particle positions, and it extends to a near-linear time algorithm for general bounded-range repulsive potentials, given additional knowledge on the rate of correlation decay.

Finally, the paper Single-Peaked Jump Schelling Games based on the master thesis of Lars Seifert was accepted at the the International Symposium on Algorithmic Game Theory (SAGT). This paper considers a game-theoretic model for residential segregation where agents strategically select their locations and may improve on their location by jumping to a suitable empty location.  In this setting, non-monotone single-peaked utilities are employed, which have recently been proposed for the setting where agents can swap locations to improve their utilities.

  • On the Giant Component of... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Ruff, Janosch; Zeif, Ziena On the Giant Component of Geometric Inhomogeneous Random GraphsEuropean Symposium on Algorithms (ESA) 2023: 20:1–20:13
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
     
  • Perfect Sampling for Hard... - Download
    Anand, Konrad; Göbel, Andreas; Pappik, Marcus; Perkins, Will Perfect Sampling for Hard Spheres from Strong Spatial MixingInternational Conference on Randomization and Computation (Random) 2023: 38:1–38:18
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
     
  • Single-Peaked Jump Schell... - Download
    Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Seifert, Lars Single-Peaked Jump Schelling GamesInternational Symposium on Algorithmic Game Theory (SAGT) 2023
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]