News
Next Seminar (2/12/2022, 10.30am): «From Combinatorial Optimization to Combinatorial Generation»
Arturo Merino, PhD(c) at Technische Universität Berlin (Germany), MSc. on Applied Math, Universidad de Chile.
ID Zoom: 98844302627
Combinatorial generation is the task of computing all solutions to a combinatorial problem instead of only one of them. For example, we may be interested in all spanning trees of a given graph or all optimal weight perfect matchings of a given weighted graph. In recent years, there has been much interest in unifying techniques or general approaches that simultaneously apply to various combinatorial generation problems. We propose a new simple general approach for combinatorial generation. Given some binary strings X⊆{0,1}ⁿ, our approach consists of greedily computing a Hamilton path in a polytope with X as vertices, namely conv(X). Our main result shows that this approach works for all X⊆{0,1}ⁿ and is efficient whenever optimization over X can be efficiently solved, showing an unexplored relation between combinatorial optimization and generation. More specifically, if we can solve certain linear optimization problems for X in time O(T), we can compute a Hamilton path in conv(X) in roughly O(T⋅log(n)) time per vertex. As a consequence, we obtain new efficient algorithms for combinatorial generation problems that can be binary encoded, like spanning tree generation, 0/1 vertex enumeration, and perfect matching generation. Furthermore, consecutive objects visited by our generation algorithms differ only in one local operation, like an edge exchange in the case of spanning trees or an alternating cycle exchange in the case of perfect matchings. This is joint work with Torsten Mütze.
Next Seminar (17/11/2022, 10.30am): «Estimates of the collective immunity to COVID-19 derived from a stochastic cellular automaton based framework»
Pedro P. B. de Oliveira, Adjunct Professor, Faculdade de Computação e Informática, Universidade Presbiteriana Mackenzie (Sao Paulo, Brasil).
ID Zoom: 95379368546
In the context of the propagation of infectious diseases, when a sufficient degree of immunisation is achieved within a population, the spread of the disease is ended or significantly decreased, leading to collective immunity, meaning the indirect protection given by immune individuals to susceptible individuals. Here we describe the estimates of the collective immunity to COVID-19 from a stochastic cellular automaton based model designed to emulate the spread of SARS-CoV-2 in a population of static individuals interacting only via a Moore neighbourhood of radius one, with a view to analyze the impact of initially immune individuals on the dynamics of COVID-19. This impact was measured by comparing a progression of initial immunity ratio—the percentage of immunised individuals before patient zero starts infecting its neighbourhood—from 0 to 95% of the initial population, with the number of susceptible individuals not contaminated, the peak value of active cases, the total number of deaths and the emulated pandemic duration in days. The influence of this range of immunities over the model was tested with different parameterisations regarding the uncertainties involved in the model such as the durations of the cellular automaton states, the contamination contributions of each state and the state transition probabilities. A collective immunity threshold of 55% +- 2:5% on average was obtained from this procedure, under four distinct parameterisations, which is in tune with the estimates of the currently available medical literature, even increasing the uncertainty of the input parameters.
Next Seminar (11/11/2022, 10.30am): «Contact process with aperiodic temporal disorder»
André P. Vieira, Profesor Asociado, Instituto de Física, Departamento de Física Geral, Universidade de São Paulo, Brasil.
ID Zoom: 97912982114
The contact process [T. E. Harris, Annals of Probability 2, 969 (1974)] is a stochastic process which can be interpreted as a model for the spreading of an infectious disease. In this process, the agents seating on the sites of a regular lattice can be either infected or susceptible. Infected agents heal with a rate m, while susceptible agents having a fraction x of infected neighbors become infected with a rate xl. For a fixed value of m, there is a critical value of l separating an active phase, in which the infection fails to propagate throughout the lattice, from an active phase, in which the infection becomes endemic. The critical point is characterized by a set of critical exponents in the directed-percolation universality class and, in particular, the critical fraction of infected agents decays as a power law of time with vanishing relative noise. In this talk, we report on the effects, on this phase transition, of imposing time-dependent rates following aperiodic but deterministic sequences obtained from substitution rules [Fogg et al., Substitutions in Dynamics, Arithmetics, and Combinatorics, Springer (2002)] such as a→ab, b→a, which yields the celebrated Fibonacci sequence abaaba…. Dependending on the strength of the temporal fluctuations induced by a sequence, we show that the critical exponents can be affected and that the critical point can be associated with huge density fluctuations characterized by an infinitely broad probability distribution.
Ph.D. in Complex Systems Engineering
PROGRAMA ACREDITADO POR LA CNA
- Diagonal Las Torres 2640, Peñalolén
- (56 2) 2331 1553