Origins of NP and P (Distinguished Lecture)
NP and P have origins in “the marriage theorem”:
A matchmaker has as clients the parents of some boys and some girls where some boy-girl pairs love each other.
The matchmaker must find a marriage of all the girls to distinct boys they love or else prove to the parents that it is not possible. The input to this marriage problem is usually imagined as a bipartite graph G with boy nodes, girl nodes, and edges between them representing love.
A possible legal marriage of some of the girls to some of the boys is represented by a subset M of the edges of G, called a matching.
The matchmaker’s problem is to find a matching which hits all the girl nodes Or else prove to the parents that there is none…
Full announcement at https://thor.inesc-id.pt/jack.edmonds/
Jack Edmonds is one of the creators of combinatorial optimization. He attended George Washington University before pursuing graduate study at the University of Maryland. He received his master’s degree in 1959 and began work at the National Bureau of Standards (NBS). He moved to the University of Waterloo in 1969, where he supervised a dozen PhD students. Throughout his career, he has influenced and assisted numerous young researchers. In the 1960s, Jack Edmonds developed a theory of matroid partition and intersection that still stands as one of the most profound and thorough explorations in the field. He illustrated the deep interconnections between combinatorial minmax theorems, polyhedral structure, duality theory, and efficient algorithms. He published many influential papers on these topics, with the one published in 1972 on theoretical improvements in algorithmic efficiency for network flow problems with Richard Karp leading to one of the most well known algorithms among nowadays CS students. He was awarded the John von Neumann Theory Prize for his contributions as a researcher and educator in 1985. Jack Edmonds retired from teaching in 1999 and was elected into the inaugural Fellows class of the Institute for Operations Research and the Management Sciences.
Alexandre Paulo Lourenço Francisco
FA3 – Informatic Department – IST Alameda
Workshop Metabolism and mathematical models: Two for a tango
Dates: November 18-19, 2021
Location: This workshop will be held in a virtual way
The topic of this workshop is metabolism in general, with a special focus, although not exclusive, on parasitology. Besides an exploration of the biological, biochemical and biomedical aspects, the workshop will also aim at presenting some of the mathematical modelling, algorithmic theory and software development that have become crucial to explore such aspects.
This workshop is being organised in the context of two projects, both with the Inria European Team Erable. One of the projects involves a partnership with the University of São Paulo (USP), in São Paulo, Brazil, more specifically the Institute of Mathematics and Statistics (IME) and the Institute of Biomedical Sciences – Inria Associated Team Capoeira – and the other involves the Inesc-ID/IST in Portugal, ETH in Zürich and EMBL in Heidelberg – H2020 Twinning Project Olissipo.
The workshop is open to all members of these two projects but also, importantly, to the community in general.