My research interest focuses on the design and analysis of efficient methods for combinatorial optimization problems on graphs or networks. I am interested in fast combinatorial algorithms that provide optimal or provably close-to-optimal results. Although research on
approximation algorithms started in the 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.
One of the problems I worked on this year is a version of the traditional classification problem, where we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. This problem is closely related to the multi-way cut problem, where one must find a partition of a graph into k sets given an initial assignment of certain nodes, named terminals, to these sets, in a way that cuts as few edges as possible. Intuitively, the k sets of the multi-way cut problem represent the k labels of a classification problem. However, the classification problem has a more complex objective function as the penalty for labeling two nodes differently should depend on the identities of the labels they receive. Additionally, we wish to use assignment costs between the nodes and the labels. The resulting labeling problem is equivalent to a type of uncapacitated quadratic assignment problem. In joint work with Jon Kleinberg we give an O(log k loglog k)-approximation algorithm, where k is the number of labels. In joint work with Anupam Gupta we improve the result for a special case that is important in vision. We give a much faster 4-approximation algorithm if the metric is the truncated linear metric.
A question related to networking is that of routing paths in networks with explicit fairness conditions. We investigated how fairness criteria interact with the optimization of network utilization. Consider the problem where a number of sources want to send flow to a single destination. We measure network utilization by the total amount of flow sent, and we use the notion of max-min fairness: a flow is max-min fair if there is no way to increase the amount of flow sent from any source without decreasing the flow sent from a source sending lesser or equal amount. The basic question then is this: how much is the maximum flow value affected by the requirement that the flow has to be max-min fair? If we allow fractional flows there is a max-min fair maximum flow. In joint work with Jon Kleinberg and Yuval Rabani we considered an “integer” counter part of this problem on networks with unit capacities, where flow for each source must be routed on a single path. Finding a max-min fair single path routing is NP-hard; however, we show that a “discretized” version of the fairest routing problem, where we allow only flow amounts that are inverse powers of two, can be solved in polynomial time. This leads to an approximately max-min fair solution for the general case.
[On sabbatical leave 1999-2000.]
Member: Fields of Operations Research and Applied Mathematics.
Program Committee Member: Workshop on approximation algorithms (APPROX 2000); Approximation and Randomization Algorithms in Communication Networks (ARACNE 2000).
Panel Member: Challenges for Theoretical Computer Science, STOC, Portland, OR, May 2000.
Combinatorics Panel Member: 2002 International Congress of Mathematicians.
External Advisory Board Member: DIMACS. Co-organizer: DIMACS workshop on Approximation Algorithms, February 2000; DIMACS Special Year on Complexity, 1999-2000. Advisory Board Member: DIMACS Special Year on Networks, 1999-2000.
Area Editor: Discrete Optimization for Mathematics of Operations Research.
Editor: SIAM Journal of Computing; Combinatorica; Journal of Theoretical Computer Science; Journal of Interconnection Networks.
Associate Editor: Mathematical Programming.
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. 40th Annual IEEE Symposium on the Foundations of Computer Science (FOCS ’99), October 1999.
Fairness in Routing and Load Balancing. 40th Annual IEEE Symposium on the Foundations of Computer Science (FOCS ’99), October 1999.
Approximation Algorithms for Some Clustering and Classification Problems. Distinguished lecture series. University of Washington, November 1999.
—. Microsoft Research, November 1999.
—. 10th Annual International Symposium on Algorithms and Computation (ISAAC 1999), Madras, India, December 1999.
A Flow-based Constant-factor Approximation Algorithm for a Classification Problem. Workshop on Approximation Algorithms, Madras, India, December 1999.
Approximation Algorithms for Some Classification Problems. IBM Almaden Research Center, January 2000.
Fairness in Network Routing. Microsoft Research, May 2000.
Challenges in Algorithm Design. Workshop on Challenges for Theoretical Computer Science, Portland, OR, May 2000.
A Constant Factor Approximation Algorithm for a Class of Classification Problems. In 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), May 2000.
“Separating Maximally Violated Comb Inequalities in Planar Graphs.” Mathematics of Operations Research (24/1) (1999), 130–148 (with L. Fleischer).
“Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields.” 40th Annual IEEE Symposium on the Foundations of Computer Science (FOCS ’99) (October 1999), 14–23 (with J. Kleinberg).
“Fairness in Routing and Load Balancing.” 40th Annual IEEE Symposium on the Foundations of Computer Science (FOCS ’99) (October 1999), 568–578 (with J. Kleinberg and Y. Rabani).
“The Quickest Transshipment Problem.” Mathematics of Operations Research (February 2000), 36-62 (with B. Hoppe).
“A constant factor approximation algorithm for a class of classification problems.” 32nd Annual ACM Symposium on Theory of Computing (STOC 2000) (May 2000), 652-658 (with A. Gupta).
“Allocating Bandwidth for Bursty Connection.” SIAM Journal on Computing (31/1) (2001), 191-217 (with J. Kleinberg and Y. Rabani).