PhD Eotvos Univ., Hungary, 1984
My research interest focuses on the design and analysis of efficient
methods for combinatorial optimization problems on graphs or networks. I am mostly
interested in fast combinatorial algorithms that provide provably close-to-optimal results
for NP-hard problems. An important area of applications is the design, maintenance, and
management of high-speed communication networks. These networks, the most important
communication platform of the future, present new technological challenges.
|The essence of many of these technological
problems is the intractability of certain simple network problems, such as routing,
bandwidth allocation, packet scheduling, and network design. My research goal is to
develop methods to deal with these simple network problems; these algorithms can serve as
tools for successfully answering the new technological challenges.
I spent the most time working on the disjoint paths
problem, the combinatorial essence of the routing problem. This problem is important for
its applications to large-scale communication networks, but it is also one of the most
basic algorithmic questions (it is one of Karp's original NP-complete problems) and has
been studied extensively since the 1960's. Despite a lot of work, there is very little
known about finding close-to-optimal routing in general classes of networks.
Two other areas that I have worked on are the
bandwidth allocation problem and network design. J. Kleinberg, Y. Rabani and I undertook
the first study of the issues inherent in statistical multiplexing from the perspective of
ACM Fellow 1998
Program Committee Member: Int. Mathematical
Programming Symp., 1997 DIMACS External Advisory Board 1996-1999
Editor: SIAM J. Computing, Electronic J.
Theoretical Computer Science, Combinatorica
Associate Editor: Mathematics of Operations
Research, Mathematical Programming A
Flows in networks. Invited Lecture, SIROCCO'98,
Flows in networks. Invited lecture, DIMACS
workshop on large scale optimization, May 1998.
Using linear programming in approximation
Algorithms. Budapest, March 1998.
Routing in networks. Invited Semiplanary lecture,
Mathematical Programming Symp., Lausanne, Aug. 1997. Simple maximum flow algorithms in
lossy networks, Symp. Integer Programming and Combinatorial Optimization (IPCO), June