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
IEEE International Conference on Software Testing, Verification and Validation (ICST) 2020
IEEE International Conference on Software Testing, Verification and Validation (ICST) 2020 will take place between the 24th and 28th of October at Alfândega Porto Congress Centre, in Porto.
ICST 2020 aims to supply a common forum for researchers, scientists, engineers and practitioners all over the world to present their latest research findings, ideas, developments and applications in the area of Software Testing, Verification and Validation.
Energy Virtual Experience – EVEx 2020
The event “Energy Virtual Experience” ( EVEx 2020) will take place online, from 23rd to 27th November 2020.
“Energy Virtual Experience” will provide 4 different interactive experiences: EVEx Talks, EVEx MasterClass, EVEx Academy, and EVEx Expo/Busines. These four experiences will be centered on “Ibero-American post-pandemic energy transition”.
Looking to stimulate interdisciplinary studies and innovative solutions in energy area, call for papers and projects will be launched soon.
INESC-ID researcher and IST Professor, Rui Castro, is member of the scientific committee of EVEx 2020.
|More information will be coming soon|