Eva Tardos
Professor
eva@cs.cornell.edu
http://www.cs.cornell.edu/home/eva/eva.html
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 closeto optimal results for NPhard problems. Although research on polynomial time approximation algorithms started in 1970s soon after the discovery of
NPcompleteness, it has truly blossomed only in the past decade. Amazing progress has 

occurred both in our ability to design approximation algorithms, and in proving limits to
approximability. Over the last year I have been working on different approximation algorithms on various basic
combinatorial problems motivated by applications arising in vision, networking and clustering.
The kmedian problem is one of the most
wellstudied clustering problems, i.e., those
problems in which the aim is to partition a given set of points into clusters so that the points
within a cluster are relatively close with respect
to some measure. For the metric kmedian
problem, we are given n points in a metric
space. We select k of these to be cluster centers, and
then assign each point to its closest
selected center. If point j is assigned to
a center i, the cost incurred is
proportional to the distance between i
and j. The goal is to select the
kcenters that minimize the sum of the
assignment costs. In joint work with
Moses Charikar, Sudipto Guha and
David Shmoys we present the first
constantfactor approximation
algorithm for this problem.
In joint work with Ashish Goel,
Monika Henzinger, and Serge Plotkin
we study the problem of scheduling
data transfers in a network. We
combine techniques from machine
scheduling and routing in network to
provide good approximation algorithms.
The network design problems model
the problem of designing networks that
have hight tolerance of edge failures.
The problem is to find a minimum cost
subgraph such that for each vertex set
S there are at least f(S) arcs leaving
the set S. In the last 10 years general
techniques have been developed for
designing approximation algorithms for
undirected network design problems.
The main techniques used for the
undirected problems do not extend to
the directed case. In joint work with
my student Vardges Melkonian we
present a 2approximation algorithm
for the class of directed network
design problems, where the function f
is crossing supermodular.
Awards
University Activities

Fields of Operations Research
and Applied Mathematics

Membership committee: Center
for Applied Math.
Professional Activities

Chair: Prize committee for the
1999 Knuth Prize.
 DIMACS External Advisory
Board member, 19961999

Coorganizer: DIMACS
workshop on Approximation
Algorithms, Spring 2000.
Advisory board member for the
DIMACS special year on
Networks in 19962000.
 Coorganizer: DIMACS special
year on Complexity in19992000
 Area editor: Discrete
Optimization of Mathematics
of Operations Research
 Editor: SIAM Journal
Journal Theoretical
Computer Science,
Combinatorica, Journal of
Interconnection Networks
 Associate Editor:
Mathematical Programming
Lectures
 Constant approximation for
kMedian. IBM Research, Almaden,
Nov 1998. Efficient resource management in high
speed networks. SPAWAR, ONR
grantees meeting, Jan. 1999.

Approximation for the kmedian and
other clustering problems. DIMACS
Distinguished Lecture Series, Rutgers
Univ., Dec. 1998.

—. Institute of Advanced Studies,
Princeton, March 1999.

—. Technion, Israel, March 1999.

—. Weizmann Institute, Israel, March
1999.

A constantfactor approximation
algorithm for the kmedian problem. The 31st Annual ACM Symposium
on the Theory of Computing, Atlanta, Georgia, May 1999.
 Scheduling data transfers in a network
and the set scheduling problem. The
31st Annual ACM Symposium on the
Theory of Computing, Atlanta,
Georgia, May 1999.
 Approximation algorithms for a
directed network design problem. The
7th International Integer Programming
and Combinatorial Optimization
Conference, Graz, Austria, June
1999.
Publications

Approximation algorithms for a
directed network design problem.
Proceedings of the 7th
International Integer Programming
and Combinatorial Optimization
Conference (June 1999), 345360
(with V. Melkonian).

Approximations for the disjoint paths
problem in highdiameter planar
networks. Journal of Computer and
System Sciences 57, STOC'95
special issue, 1 (1998), 6173 (with J. Kleinberg).

A constantfactor approximation
algorithm for the kmedian problem.
Proceedings of the 31st Annual
ACM Symposium on the Theory of
Computing (May 1999), 110 (with
M. Charikar, S. Guha, and D. Shmoys).
 Scheduling data transfers in a network
and the set scheduling problem.
Proceedings of the 31st Annual
ACM Symposium on the Theory of Computing (May 1999), 189198
(with A.Goel, M. Henzinger, and S. Plotkin).
