search

All

Around the Petersen Colouring Conjecture Wed, Feb 19, 2020 12:30 CET

Speakers: Jean-Sébastien Sereni

A number of old conjectures related to edge-colourings of 3-regular graphs remain vastly open. Among them, the Petersen colouring conjecture is a very strong statement, which implies most of these, such as the Berge—Fulkerson conjecture, and the 5-Cycle-double-cover conjecture. It states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge e, the set of colours assigned to the edges adjacent to e has cardinality either 2 or 4, but not 3.

Bipartite Diameter and Other Measures Under Translation Thu, Nov 21, 2019 12:30 CET

Speakers: Boris Aronov

Let A and B be two sets of points in R^d, where |A|=|B|=n and the distance between them is defined by some bipartite measure dist(A,B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are (i) the diameter in two and three dimensions, that is diam(A,B) = max {d(a,b) : a in A, b in B}, where d(a,b) is the Euclidean distance between $a$ and $b$,

JGA 2019
21ièmes Journées Graphes et Algorithmes (JGA 2019) Wed, Nov 13, 2019 11:00 CET (CONFIRMED)

Les 21ièmes Journées Graphes et Algorithmes (JGA 2019) auront lieu à Bruxelles, du 13 au 15 novembre 2019. Il s'agit du rendez-vous annuel de la communauté francophone de la théorie des graphes et de ses applications.

On Grammars, Polytopes, and Groups Fri, Nov 8, 2019 12:30 CET

Speakers: Mateus de Oliveira Oliveira

A fundamental step towards solving combinatorial problems using techniques from linear programming theory is to encode the space of feasible solutions for such problems as the set of vertices of polytopes of small extension complexity. In this work, we establish several connections between the extension complexity of polytopes, formal language theory, and group theory. In particular, we introduce the notion of homogeneous context-free grammars and show that polytopes corresponding to languages accepted by polynomial-size non-uniform families of grammars with polynomial homogeneity have polynomial extension complexity.

Coloring and Maximum Weight Independent Set of rectangles Wed, Nov 6, 2019 12:30 CET

Speakers: Bartosz Walczak

We prove that every intersection graph of axis-parallel rectangles in the plane with clique number ω has chromatic number O(ω log ω), which is the first improvement of the original O(ω²) bound of Asplund and Grünbaum from 1960. As a consequence, we obtain a polynomial-time O(log log n)-approximation algorithm for Maximum Weight Independent Set in axis-parallel rectangles, improving the previous best approximation ratio of O(log n/log log n). Joint work with Parinya Chalermsook.

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank Wed, Sep 11, 2019 12:30 CEST

Speakers: Makrand Sinha

Chattopadhyay, Mande and Sherif (to appear in STOC 2019) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture.

3D Snap Rounding Wed, Jun 19, 2019 12:30 CEST

Speakers: Leo Valque

Many computational geometry algorithms require greater accuracy for output than for input. So, to send or use the output, we often need to round it off. If this is done naively, intersections can occur during rounding. An algorithm from Devillers, Lenhart, Lazard was presented last year to solve this problem. The worst case of this algorithm is \(O(n^15)\). An implementation of this algorithm shows that on average, it is \(O(n \sqrt{n})\).

A time- and space-optimal algorithm for the many-visits TSP Wed, May 29, 2019 12:30 CEST

Speakers: Matthias Mnich

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kcof times. Travel costs may not be symmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984).

Location Information Thu, May 23, 2019 12:30 CEST

Speakers: Maarten Löffler

Let P be a set of n points in the plane. In the traditional geometric algorithms view, P is given as an unordered sequence of locations (usually pairs of x and y coordinates). There are many interesting and useful structures that one can build on top of P: the Delaunay triangulation, Voronoi diagram, well-separated pair decomposition, quadtree, etc. These structures can all be represented in O(n) space but take Omega(n log n) time to construct on a Real RAM, and, hence, contain information about P that is encoded in P but cannot be directly read from P.

In this talk I will explore the question how much information about the structure of a set of points can be derived from their locations, especially when we are uncertain about the locations of the points.

Maintaining Perfect Matchings at Low Cost Fri, May 10, 2019 12:30 CEST

Speakers: Jannik Matuschke

The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, adding two nodes to the input might change the optimal solution completely. On the other hand, one expects that small changes in the input should incur only small changes on the constructed solutions, measured as the number of modified edges.