Linda Cook: 200,000 Colors Suffice (for t-Perfect Graphs). Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities. In 1975, V. Chvátal defined an analogous class called t-perfect graphs, which are the graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. We show that t-perfect graphs are 199,053-colourable. This is the first finite bound on the chromatic number of t-perfect graphs, and answers a question of B. Shepherd from 1995. Our proof is mainly graph theoretic. Our bound is probably not tight. M. Laurent and P. Seymour gave an example of a t-perfect graph requiring four colors in the 1990's. It is open whether all t-perfect graphs are 4-colorable. Moreover, a stronger conjecture by A. Sebő that every triangle-free t-perfect graph is 3-colorable remains open as well. Joint work with: Maria Chudnovsky (Princeton), James Davies (Cambridge), Sang-il Oum (IBS DIMAG), Jane Tan (Oxford). Available at: https://arxiv.org/abs/2412.17735
Yan Gerard: Shadok Heuristics for Geometric Optimization Challenges. The Geometric Optimization challenge CG:SHOP (Computational Geometry: Solving Hard Optimization Problems) held its inaugural edition in 2019, featuring a variant of the renowned Traveling Salesman Problem (TSP). The objective was to minimize or maximize the area of a simple tour. Since its inception, the Shadok team has participated annually until 2024, with various team configurations [Pascal Lafourcade (2021) - Luc Libralesso (2021) - Aldo Gonzalez-Lorenzo (3 times) - Loïc Crombez (4 times) - Y.G. (5 times) - Guilherme Da Fonseca (every edition)]. The team's rankings over the years have been: 2nd, 4th, 1st, 1st, 2nd, and 1st. The goal of the talk is to present several heuristics developed by the team, with a particular focus on the conflict-based meta-heuristics successfully employed in 2021 and 2022 for two distinct problems. We will discuss how to practicaly and approximatively solve four problems: "TSP variant", Multi-Agent Path Finding, (Intersection) Graph Coloring and Packing.
Mathieu Mari: Piercing Pseudo-Disk Rectangles Online. We consider the Online Piercing of Rectangles problem, where given a fixed underlying grid of n points in the plane, a sequence R of axis-parallel rectangles arrives in an online fashion, and an online algorithm must maintain a hitting set at any time, which is a set P of points of the grid such that every rectangle that has arrived so far must contain at least one point from P. Each time a rectangle arrives, the algorithm can add as many points as necessary but cannot remove points added previously. This problem was initially considered by Alon, Awerbuch, and Azar (STOC '03) in its most general version, where rectangles are replaced by a set of m arbitrary hyperedges of fixed set of points. They present a O(log n log m)-competitive algorithm, and an almost tight lower-bound. Since then, several works have considered restrictions to geometric cases (squares, disks, etc) and provided optimal O(log n)-competitive algorithms. However, all cases where an optimal competitive algorithm is known so far correspond to fat objects, and a difficult open question is to provide a O(log n)-competitive algorithm for rectangles, which probably form the simplest class of non-fat objects. Toward this goal, we provide a O(log n)-competitive algorithm when the rectangles form a system of pseudo-disks (i.e., without crossings). This requires a specific approach to take advantage of the underlying planarity of pseudo-disks. We also provide a simple O(log n)-competitive algorithm for the crossing-only case, which may be a positive sign for the existence of a O(log n)-competitive algorithm for the general case of axis-parallel rectangles.
Daria Pchelina: Optimal Disc and Sphere Packings. How can we arrange an infinite number of spheres to maximize the proportion of space they occupy? Kepler conjectured that the "cannonball" packing is the optimal way to do it. This conjecture remained unproved for almost 400 years until Hales and Ferguson provided a 250-page proof accompanied by hundreds of thousands of lines of computer code. Given an infinite number of coins of three fixed radii, how can we place them on the plane to maximize the proportion of the covered surface? A disc packing is called triangulated if its contact graph is triangulated. We identified optimal packings for several triplets of disc sizes, all of which are triangulated. Conversely, we also showed that for certain other triplets, no triangulated packing is optimal. Building on our expertise in multi-size disc packings, we extend our research to two-sphere packings in 3D. Simplicial sphere packings are those whose contact graphs form pure simplicial 3-complexes. We consider the only ratio of sphere sizes that allows such packings which are conjectured to be optimal.
Lukas Vogl: The Cluster LP for Correlation Clustering. Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizing the number of inter-cluster edges plus the number of missing intra-cluster edges. In this talk, I will present the cluster LP, a strong linear program that might tightly capture the approximability of correlation clustering. It is exponentially sized, nevertheless, we show that the cluster LP can be (1+eps)-approximately solved efficiently. We achieve a (1.437+eps)-approximation algorithm by rounding the cluster LP. Moreover, all of this can be done in sublinear time bridging the gap between state-of-the-art approximation algorithms and the recent focus on fast algorithms. Based on joint work with Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Shuyi Yan, Hanwen Zhang.