Welcome to the homepage of the
The MTA-ELTE Egerváry Research Group (EGRES for short) is led by András Frank. The group's main field of research is theoretical combinatorial optimization (for a detailed account, see Introduction). EGRES is affiliated with Operations Research Department, Eötvös University, Budapest, and the Hungarian Academy of Sciences.
For more information on our research, see our Technical Reports and Quick Proofs series. Visit our Egres Open website, an open problem collection intended also as a discussion forum for fellow researchers (the old problems page can be found here). For publicaton lists see the individual members pages.
Our mail address is: EGRES Group, Operations Research Department, Eötvös University, Pázmány P. s. 1/C, Budapest, Hungary, H-1117.
For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a "black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm: http://arxiv.org/abs/1210.4594
In the interest of covering all the ideas, we will assume that the audience is familiar with basic notions such as augmenting paths and bipartite matching algorithm.
We are deeply saddened by the death of Laci Szegő, who passed away on May 15 after a long illness. He was a dear friend and colleague whose mathematical accomplishments and wonderful personality were an inspiration to all of us.
Kristóf Bérczi received the Young Researcher Prize of the Hungarian Academy of Sciences on February 25, 2013.
The current problem of the season on Egres Open is Disjoint strongly connected spanning subgraphs.
After some hiatus, the "Problem of the month" feature of Egres Open returns under the new name "Problem of the season".
The Hungarian Academy of Sciences (MTA) will provide increased financial support for the Egerváry Research Group in the period 2012-2016. EGRES is one of the three supported mathematics research groups.
András Frank's new book Connections in Combinatorial Optimization is now available from Oxford University Press. The book offers a unified treatment of developments in the concepts and algorithmic methods of combinatorial optimization, starting from basic results on graphs, matroids and polyhedral combinatorics, through the advanced topics of connectivity issues of graphs and networks, to the abstract theory and applications of submodular optimization.
We are pleased to report that László Végh received this year's Danny Lewin Best Student Paper Award at STOC for his paper Augmenting undirected node-connectivity by one. Congratulations!
Please visit Egres Open, the new open problem forum of EGRES. In addition to being an open problem collection, it features surveys on selected topics, background information including theorems and definitions, and discussion forums for every page where anyone can comment on the open problems and surveys.
We are pleased to report that Gyula Pap received the Junior Prima Prize in the "Hungarian Science" category. The prize is given every year to 10 young Hungarian researchers for exceptional achievements. Congratulations, Gyuszkó!
There will be a meeting at ELTE on the 5th and 6th of June on the occasion of András Frank's 60th birthday, with talks by some of his former students. You can find the program here.
Tamás Király received the Young Researcher Prize of the Hungarian Academy of Sciences on March 18, 2009.
András Frank received the Szent-Györgyi Prize from the Minister of Education on January 22, 2009.
We at EGRES are all very glad to learn that our colleague Zoltán Király received the Best Paper Award of the 16th Annual European Symposium on Algorithms for his paper "Better and simpler approximation for the stable marriage problem". Zoli, congratulations! Your success is extremely encouraging for the whole group.
In the past four years, the Egerváry Research Group participated in the ADONET European Marie Curie Research Training Network, which enabled the invitation of several young researchers to Budapest. The following researchers have been visiting EGRES within the framework of ADONET: Saverio Caminiti, Hans-Florian Geerdes, Dion Gijswijt, Ambros Gleixner, Gwenaël Joret, Vincent Jost, Lavanya Kannan, Lap Chi Lau, and Nguyen Tien Thanh.
EGRES starts to publish a new online series called EGRES Quick-Proofs, which intends to be a forum for the publication of short proofs, notes, and minor results that are not substantial enough to be published as a separate paper. For more details, see the Quick-Proofs page.
In the next three years, the Hungarian Academy of Sciences (MTA) will provide increased financial support for EGRES, including the funding of 3 full-time research positions.
The ADONET/COST293 Spring School on Combinatorial Optimization and Communication Networks, organized partly by EGRES, will be held in Budapest on 20-24 March, 2006. More information is available on the web page of the spring school.
LEMON (Library of Efficient Models and Optimization in Networks) is a C++ template library aimed at combinatorial optimization tasks, especially those working with graphs and networks. The LEMON project is launched by the EGRES group. The project is led by Alpár Jüttner. LEMON is an open source project.
EGRES participates in Algorithmic Discrete Optimization Network (ADONET), a Marie Curie Research Training Network funded by the European Union FP6 Programme. The network consists of research teams and researchers from Germany, Belgium, the Netherlands, Italy, France, Switzerland, Portugal, the United Kingdom, Austria, and Hungary.