Tag: Plateau seminar

Recherche Opérationnelle à Google

-- Laurent Perron (Google)

summary: A travers une série d'exemples, je décrierai les applications de la recherche opérationnelle et de l'optimisation discrète à Google. Puis je me focaliserai sur l'apport récent des techniques des moteurs SAT (satisfiabilité) et les challenges et opportunités qui lui sont liées.

Matchings and related structures with Specified Color Properties In Vertex- or Edge-colored Graphs.

-- Yannis Manoussakis (University Paris South and CNRS)

summary: We consider problems in edge- or vertex colored graphs. As an example, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.). When the edges/vertices of graphs are ...

The Domino Problem is undecidable on surface groups

-- Nathalie Aubrun (ENS lyon)

summary: The domino problem for a finitely generated group asks whether there exists an algorithm which takes as input a finite alphabet and finitely many Wang tiles, and decides whether there exists a tiling of the group by this set of tiles. I will survey known results and present the ...

VERTEX DISTINGUISHING COLORINGS OF GRAPHS

-- Professor Mariusz Wozniak (Department of Discrete Mathematics, AGH University, Cracow, Poland)

Abstract : Let us consider a coloring \(f\) of edges in a simple graph \(G = (V, E)\). Such acoloring defines for each vertex \(x \in V\) the palette of colors, i.e., the multiset of colors of edges incident with \(x\), denoted by \(S(x)\). These palettes can be used to ...

The coloring problem in clique-hypergraphs of graphs

-- Pr. Liying Kang (Department of Mathematics, Shanghai University, China)

ABSTRACT: A maximal clique of a graph is a clique not properly contained in any other clique. A \(k\)-clique coloring of a graph is an assignment of a \(k\) colors to the vertices of \(G\) such that no maximal clique with at least two vertices is monochromatic. The clique-chromatic ...

Minimizing the number of unhappy singles

-- Chien-Chung Huang (Gothenburg)

Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B ranks its neighbors in an order of preference, perhaps involving ties.

A matching M is said to be stable if there is ...

Prophet inequalities and secretary problem: a new approach.

-- Nguyen Kim Thang (IBISC)

In the setting of prophet inequalities and secretary problem, one observes a sequence of random objects and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The objective is to maximize the reward while observing the objects in an online manner ...

Complexité de comptage des opérateurs d'intégration

-- Hugo Férée (Université de Lille)

L'analyse récursive est un domaine qui s'attache à comprendre la notion de calcul sur des ensembles non dénombrables comme les nombres réels ou les fonctions réelles par exemple. Il permet entre autres de définir une notion de complexité sur de tels ensembles, mais les classes de complexité associées ...

Universal computation and asymptotic behaviour in symbolic dynamics.

-- Benjamin Hellouin (Universidad Andrés Bello (Santiago))

Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding ...

Highly Resource-limited Distributed Systems

-- Matthias Függer (Max-Planck-Institut)

In this talk I would like to advocate the study of non-classical distributed systems whose computing nodes can perform only simple computations under highly restricted communication mechanisms and memory capabilities.

I will present two problems, we are currently working on, one from chip design and one from biology, showing that ...

Page 1 / 2 »