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. gecco-wg

22.05.2024

Three Papers accepted at GECCO and WG

We are proud to announce three recently accepted papers, two of which as full papers and one as a poster. The Genetic and Evolutionary Computation Conference (GECCO) in Melbourne, Australia on 14-18 July, will feature the paper Run Time Bounds for Integer-Valued OneMax Functions. In this paper, the authors consider the search space \(Z^n\), while most theoretical run time analyses of discrete randomized search heuristics focus on finite search spaces. They give theoretical and empirical analyses on the (1+1) EA and the RLS with different mutation operator optimizing a fitness functions defined on the infinite search space \(Z^n\). Additionally, the paper Algorithm Performance Comparison for Integer-Valued OneMax was accepted as a poster.

For the International Workshop on Graph-Theoretic Concepts in Computer Science (WG) on 19-21 June in Gozd Martuljek, Slovenia our group members wrote the paper A New Approach for Approximating Directed Rooted Networks. In this paper the authors consider the k-outconnected dirested Steiner tree problem (\(k\)-DST). In particular, given a directed edge weighted graph with a set of vertices as terminals and a vertex as root, the goal is to find the minimum cost subgraph of the graph such that there are k edge-disjoint paths from the root to each terminal. Inspired by modern day applications such as video streaming, the paper focuses on developing efficient algorithms for \(k\)-DST when the majority of nodes are terminals. The authors provide the first approximation algorithm for \(k\)-DST on such graphs, in which the approximation ratio depends (primarily) on the size of non-terminal nodes. They also present a randomized algorithm that finds a solution of weight at most \(O(k|S| log |T|)\) times the optimal weight, and with high probability runs in polynomial time.