We investigate two-player win/lose games over finite graphs. In all generality, these games are concurrent, i.e. at each state of the graph, there is a concurrent interaction between the two players to determine the next state visited. In the special case where, at every state of the graph, there are no real concurrent interaction, i.e. only one player is truly playing, the game is turn-based. Various desirable properties hold on turn-based games, but do not on arbitrary concurrent games; e.g. there exist subgame optimal strategies in all prefix-independent turn-based games, while there do not in very simple prefix-independent concurrent games. A possible way to circumvent this issue is to define a subclass of concurrent games, that is a proper superclass of turn-based games, while enjoying several of their nice properties. The goal of this talk is to introduce such a subclass of concurrent games, namely finitely maximizable games, and to show step by step how we came up with this definition. The novel way that we use to define such a subclass of well-behaving concurrent games constitutes a promising approach for investigating more general concurrent games, such as non-antagonistic two-player games, or even multi-player games.
Lieu : Salle de séminaire 4B125 (bâtiment Copernic)
Philippe Gambette soutiendra son habilitation à diriger des recherches, intitulée Proximity, Similarity and Heredity: From Bioinformatics to Digital Humanities (Proximité, similarité et hérédité : de la bioinformatique aux humanités numériques), le lundi 28 octobre 2024 à 14h30, dans la salle 4B125 du bâtiment Copernic.
Plus d’informations sont fournies sur cette page.
Network design is a class of problems with wide applicability, including well-known problems such as Steiner tree and the travelling salesperson problem. In general, these problems concern the task of finding subgraphs establishing connections between nodes with some desired property, such as fault tolerance or structural constraints.
One technique that has found success in this area is the use of tree embeddings, which transform the input graph into a tree, where the problem is usually easier to solve.
However, these techniques cannot perfectly embed the graph, and thus incur a loss in the approximation factor of O(log n), even for simple input graphs such as grids, expanders, and bounded-treewidth graphs.
In this talk, we will look at a classic problem in the area of network design, the group Steiner tree problem, as well as the approximation techniques used to solve it.
We will then introduce the setting of bounded treewidth, and see how we can use this additional structure to design a lossless reduction-to-tree technique for network design problems.
Finally, we will see how this technique can be applied to group Steiner tree to break the O(log n) tree embedding barrier and obtain an optimal approximation factor (matching trees), with the running time increasing as a function of the treewidth.
This talk is based on joint work with Parinya Chalermsook, Syamantak Das, Guy Even and Bundit Laekhanukit.
Corentin Lunel soutiendra sa thèse de doctorat, intitulée Arbres, Décompositions et Théorie des Nœuds, le 23 septembre 2024 à 16h.
The Freeze-Tag Problem, introduced in Arkin et al. (SODA’02) consists of waking up a swarm of n robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the wake time of the last robot, the makespan.
Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the L1-norm, showing that a makespan of at most 5r can always be achieved, where r is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most 5r can be computed in optimal time O(n). Both bounds, the time and the makespan are optimal. This implies for the L2-norm a new upper bound of 5\sqrt{2}r \approx 7.07r on the makespan, improving the best known bound so far (5+2\sqrt{2}+\sqrt{5})r \approx 10.06r.
Along the way, we introduce new linear time wake-up strategies, that applies to any norm, and that show that an optimal bound on the makespan can always be achieved by a schedule computable in linear time.
Doriann Albertin soutiendra sa thèse de doctorat intitulée Combinatoire et géométrie des quotients de l’ordre faible le lundi 26 septembre 2022 à 17h.
Résumé :
Les treillis sont des posets où toute famille d’éléments admet un supremum et un infimum. Un treillis est sup semi-distributif dès lors que tout élément s’écrit de manière unique comme le supremum d’une antichaîne minimale pour l’inclusion et minimale dans le treillis. Cette antichaîne est la représentation sup canonique de cet élément. Un élément qui est sa propre représentation sup canonique est appelé sup irréductible. Le complexe sup canonique d’un treillis sup semi-distributif est le complexe simplicial dont les faces sont les ensembles de sup irréductibles qui forment une représentation sup canonique. Cette thèse introduit le complexe canonique d’un treillis (sup et inf) semi-distributif, qui contient les complexes sup et inf canoniques et encode tous les intervalles du treillis. Ces complexes sont compatibles avec les treillis quotients, au sens où le complexe canonique d’un quotient est le sous-complexe du complexe canonique du treillis engendré par les sup et inf irréductibles non contractés dans le quotient.
L’ordre faible sur les permutations est un exemple fondamental de treillis semi-distributif, central dans cette thèse. On utilise fortement le modèle combinatoire des arcs et des diagrammes d’arcs sans croisements développé par N. Reading pour décrire les sup irréductibles et les représentations sup canoniques de l’ordre faible.
On montre que le complexe canonique de l’ordre faible est isomorphe au complexe de semi-croisement sur les arcs. On s’intéresse ensuite aux quotients de l’ordre faible, comme le classique treillis de Tamari obtenu par la congruence sylvestre, et les treillis permusylvestres de V. Pilaud et V. Pons qui interpolent entre l’ordre faible, le treillis de Tamari et le treillis booléen. Ces treillis ont été réalisés comme graphes des permusylvèdres, qui généralisent l’associaèdre de J.-L. Loday. Ces polytopes sont des enlevoèdres, puisqu’ils sont obtenus en supprimant des inégalités de la description des facettes du permutoèdre. Cette thèse montre que parmi tous les treillis quotients de l’ordre faible, seuls les treillis permusylvestres peuvent se réaliser comme enlevoèdres, ce qui justifie la nécessité des constructions alternatives pour tous les quotientopes. Ceci amène à la description des cônes de type des éventails permusylvestres.
Abstract:
Lattices are posets where any family of elements admits a join and a meet. A lattice is join semi-distributive when every element is uniquely written as the join of an antichain minimal for the inclusion and minimal in the lattice. This antichain is the canonical join representation of this element. An element that is its own canonical join representation is called join irreducible. The canonical join complex of a join semi-distributive lattice is the simplicial complex whose faces are the sets of join irreducibles which form a canonical join representation. This thesis introduces the canonical complex of a (join and meet) semi-distributive lattice, which contains the canonical join and meet complexes and encodes all the intervals of the lattice. These complexes are compatible with lattice quotients, in the sense that the canonical complex of a quotient is the subcomplex of the canonical complex of the lattice generated by the join- and meet irreducibles that are not contracted in the quotient.
The weak order on permutations is a fundamental example of a semi-distributive lattice, central in this thesis. We extensively use the combinatorial model of arcs and non-crossing arc diagrams developed by N. Reading to describe the join irreducibles and canonical join representations of the weak order.
We show that the canonical complex of the weak order is isomorphic to the semi-crossing complex on arcs. We then focus on quotients of the weak order, such as the classical Tamari lattice obtained by the sylvester congruence, and the permutree lattices of V. Pilaud and V. Pons that interpolate between the weak order, the Tamari lattice and the boolean lattice. These lattices were realized as graphs of the permutreehedra, generalizing J.-L. Loday’s associahedron. These polytopes are removahedra as they are obtained by removing inequalities from the facet description of the permutohedron. This thesis shows that the permutree lattices are the only lattice quotients of the weak order that can be realized as removahedra, which justifies the need for alternative constructions for all quotientopes. This leads to the description of the type cones of permutree fans.