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. icaps-pakdd

23.02.2024

Two Papers accepted at ICAPS and PAKDD

We are glad to announce two recently accepted papers. The first paper Incremental Ordering for Scheduling Problems was among the 22% accepted papers for the International Conference on Automated Planning and Scheduling (ICAPS) which will take place in Banff, Canada on 1-6 June. The paper inspects two classical problems — finding a topological ordering of a directed acyclic graph and assigning resources to work packages of a scheduling problem. It does so with a new perspective: How fast can an algorithm possibly compute the first (and following) parts of a solution to a problem instance? Besides restructuring existing algorithms to solve this enumeration variant, the paper also proves optimality of the algorithm with new lower bounds on the complexity of the topological ordering enumeration problem.

Furthermore, A Contraction Tree SAT Encoding for Computing Twin-Width was accepted at The Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) on May 7-10 in Taipei, Taiwan. Twin-width is a structural width parameter and matrix invariant introduced by Bonnet et al. [FOCS 2020], that has been gaining attention due to its various fields of applications. In this paper, inspired by the SAT approach of Schidler and Szeider [ALENEX 2022], the authors provide a new SAT encoding for computing twin-width. The encoding aims to encode the contraction sequence as a binary tree. The asymptotic size of the formula under our encoding is smaller than in the state-of-the-art relative encoding of Schidler and Szeider. They also conduct an experimental study, comparing the performance of the new encoding and the relative encoding.

  • Incremental Ordering for ... - Download
    Neubert, Stefan; Casel, Katrin Incremental Ordering for Scheduling ProblemsProceedings of the International Conference on Automated Planning and Scheduling 2024: 405–413
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
     
  • A Contraction Tree SAT En... - Download
    Horev, Yinon; Shay, Shiraz; Cohen, Sarel; Friedrich, Tobias; Issac, Davis; Kamma, Lior; Niklanovits, Aikaterini; Simonov, Kirill A Contraction Tree SAT Encoding for Computing Twin-WidthAdvances in Knowledge Discovery and Data Mining 2024
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]