EGRES

Egerváry Research Group on Combinatorial Optimization


 

Eugene Egerváry (in Hungarian, Egerváry Jenő) can certainly be considered as one of the founding fathers of what is called today Combinatorial Optimization. Extending earlier works of Dénes Kőnig, his classic paper (On combinatorial properties of matrices, Mat. Lapok, 38, 1931. 16-28. (Hungarian with German summary)) describes the duality theorem for the weighted bipartite matching problem, which is called today the assignment problem, proves the integrality result, and develops the underlying idea of the first primal-dual type algorithm that is called throughout the literature the Hungarian Method, a name introduced by H. Kuhn who actually used Egerváry's ideas to develop an efficient algorithm. It is remarkable that this algorithm turned out to be strongly polynomial.
 
These ideas of Egerváry have been the prototype of a huge body of later research in areas like network flows, linear programming, matroid optimization, or matching theory. Even in as sophisticated frameworks as the submodular flows the original ideas of Egerváry could be extended.
 
Given the significance of the Hungarian Method, here in Budapest, the city of Egerváry, several researchers, seniors, post docs and Ph.D. students, felt obliged to establish a research group called Egerváry Research or, in short, EGRES. This is only an informal group not belonging to any one institution and its members actually work for several institutes. We started to run a series of EGRES technical reports to present our results. It is available here, and for request in printed form as well.
 
Our main goal is to follow the tradition laid down by Egerváry and work on combinatorial optimization problems where nice characterizations, min-max theorems and/or polynomial time algorithms can be given. Some of our central themes in combinatorial algorithms and structures are: network and graph optimization problems with special emphases on paths, trees and connectivity, matchings, matroid optimization, submodular functions and frameworks, partially ordered sets, discrete convexity. Applied or near-applied problems are also important for us. One of our basic interests is to explore further the borderline of NP-complete and polynomially solvable problem classes in combinatorial optimization.
 
We want to provide a forum for exchanging ideas and to promote research in this area. Naturally it is also our main objective to attract talented and interested newcomers.
 
In order to achieve these goals, we are going to start a homepage for open problems which will not only be a dry list but will contain motivations, links, comments, solved special cases, as well. Naturally, we would greatly appreciate any nice open problem, so if the reader wants to popularite his/her favourite problems, please send them to: frank@cs.elte.hu
 
Also, there is an Egerváry seminar on Mondays 14:00-16:00 where members give an account on recent developments. The Egerváry Research Seminar on Mondays 16:00-18:00 is a forum for exhibiting our recent research results or discuss ideas, approaches and new problems.
 
January the 2nd, 2002.

András Frank