Agenda
May
-
13:0014:00
LaBRI and Inria are joining forces as part of the University Innovation Hub and are hosting a discussion session featuring a presentation by the startup Ebiose on May 28 from 1:00 to 2:00 p.m. in the LaBRI lecture hall.
FrançaisAmphi LaBRI -
14:0015:00
In the Demand Strip Packing problem (DSP), we are given a finite set of axis-aligned rectangular items, each characterized by a specific width and height. These items need to be packed without rotation into a strip of fixed width while minimizing the peak demand: the maximum sum of heights of items placed at any point on the x-axis. We are the first to consider the online variant of the problem, where items are revealed to an algorithm one by one in a list. Upon arrival, each item must be placed on the strip irrevocably before the next item in the list is revealed. As usual in online optimization, we evaluate the performance of online algorithms using competitive analysis. We give a strictly 4.263-competitive algorithm, significantly improving upon the respective bound of 6.479 for Online Strip Packing. Additionally, we prove a lower bound of 1.812 on the absolute competitive ratio of any online algorithm for DSP and, thus, clearly separate Online DSP from Online Minimum Peak Appointment Scheduling (MPAS), a special case of Online DSP, for which a strictly 5/3-competitive algorithm is known.
This is joint work with Franziska Eberle, Georgios Moneftsis, Malin Rau, and Albert Vesterlund.
Sebastian Bruchhold (TU Berlin)
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .EnglishLaBRI/178
June
-
11:0012:00EnglishLaBRI 178
-
13:3014:30
Title: Will My Favorite Chases Terminate if Evaluating Conjunctive Queries Does? One Does Not Simply Decide This
Abstract: Existential rules are a prominent formalism to enrich a database with knowledge from the domain of interest, but make even basic reasoning tasks on the resulting knowledge base undecidable. To circumvent this, several classes of rules offering various useful properties have been identified. One such class, for instance, contains all sets of rules on which the chase algorithm always terminates, which guarantees the existence of a finite universal model. However, these classes are often abstract rather than concrete: it may be undecidable to check whether a given set of rules belongs to them. Given that the most studied classes of existential rules are designed for reasoning on databases, thus ensuring decidable conjunctive query entailment, we ask: Within a class that supports decidable query entailment, do the usual abstract classes become concrete? We answer in the negative for classes based upon the termination of all classical chase variants and for the bts class.
EnglishLaBRI -
10:0011:00EnglishLaBRI
-
14:0015:00
Software development is an inherently incremental process. To this end, most programming languages provide basic mechanisms for programmers to indicate that a given functionality is not yet implemented, for instance through dedicated exceptions. Unfortunately, apart from incremental typecheckers, most of the tools used to reason about program correctness—like testing, analysis, and verification frameworks—fail to account for these incompleteness idioms. As a result, programmers are faced with either spurious failure reports or the burden of altering their specifications, which sacrifices the direct causal connection between the code and the reasoning tools. In this talk, I will illustrate this issue in the context of testing, considering both unit testing and property-based testing, as well as certified programming in proof assistants. Examining the problem in such disparate settings allows us to isolate the core concepts required to build truly incremental reasoning tools.
Bio:
Éric Tanter is a Full Professor in the Computer Science Department of the University of Chile. He received his PhD from both the University of Nantes and the University of Chile in 2004. His research interests cover programming languages and software engineering, ranging from the theoretical underpinnings of programming languages to the empirical study of the practice of programming. Recently, he has been deeply involved in the foundations and practice of gradual typing and verification. He holds an Inria International Chair for the period 2025-2029.Salle 178 (LaBRI) -
14:0016:30EnglishLaBRI