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. focs-ppsn

17.07.2024

Two Papers accepted at FOCS and PPSN

We are proud to announce two rently accepted papers: At the 65th IEEE Symposium on Foundations of Computer Science (FOCS) in Chicago, USA on 27-30 October, one of the top conferences in computer science, the paper Improved Distance (Sensitivity) Oracles was accepted. A distance oracle (DO) is a graph data structure that can quickly retrieve the approximate distance of any two vertices, an \(f\)-distance sensitivity oracle (\(f\)-DSO) can do so even after up to \(f\) edges failed in the graph. It is known that these data structures require \(\Omega(n^2)\) space in graphs with \(n\) vertices if they have multiplicative stretch (quality of approximation) better than 3. The paper sidesteps this lower bound by introducing a small additive stretch in order to construct a distance oracle with multiplicative stretch arbitrarily close to 1 and subquadratic space. It further gives a general construction that can turn any subquadratic-space DO into an fault-tolerant \(f\)-DSO retaining the low space and with only a slight loss in stretch.

Furthermore, the paper Greedy versus Curious Parent Selection for MOEAs was accepted at the 18th International Conference on Parallel Problem Solving From Nature (PPSN). The paper considers a pair of generalized OneMax functions and show that, if the optima of the two functions are \(d\) apart, then (G)SEMO has an expected optimization time of \(O(dn\log(n))\). The authors also show that parent selection based on the curiosity-based novelty search can improve the optimization time to \(O(n^2)\) on OneMinMax. By contrast, the greedy parent selection schemes can be trapped with an incomplete Pareto front for superpolynomial time. Finally, wthe paper contains experimental results on the two-objective optimization of linear functions.