1998 - 1999 CS Annual Report                                                                  Faculty
choices.gif (4488 bytes)
 

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 close-to- optimal results for NP-hard problems. Although research on polynomial time approximation algorithms started in 1970s soon after the discovery of NP-completeness, 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 k-median problem is one of the most well-studied 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 k-median 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 k-centers that minimize the sum of the assignment costs. In joint work with Moses Charikar, Sudipto Guha and David Shmoys we present the first constant-factor 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 2-approximation algorithm for the class of directed network design problems, where the function f is crossing supermodular. 

Awards  

  • ACM Fellow 1998 
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, 1996-1999  
  • Co-organizer: DIMACS workshop on Approximation Algorithms, Spring 2000.  Advisory board member for the DIMACS special year on Networks in 1996-2000. 
  • Co-organizer: DIMACS special year on Complexity in1999-2000 
  • 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 k-Median. IBM Research, Almaden, Nov 1998. Efficient resource management in high speed networks. SPAWAR, ONR grantees meeting, Jan. 1999.  
  • Approximation for the k-median 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 constant-factor approximation algorithm for the k-median 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), 345-360 (with V. Melkonian).  
  • Approximations for the disjoint paths problem in high-diameter planar networks. Journal of Computer and System Sciences 57, STOC'95 special issue, 1 (1998), 61-73 (with J. Kleinberg).  
  • A constant-factor approximation algorithm for the k-median problem. Proceedings of the 31st Annual ACM Symposium on the Theory of Computing (May 1999), 1-10 (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), 189-198 (with A.Goel, M. Henzinger, and S. Plotkin).