Talks are held in the Gates Building, near the Main Quad of Stanford's campus. Click here for directions.
(Joint work with P.Berman.)
This work is joint with Lisa Zhang and will be presented at SODA '00.
Joint work with Sanjeev Khanna.
This talk presents joint work with Joan Feigenbaum, Sampath Kannan, and Mahesh Viswanathan. It will appear at the SODA'00 conference. A full paper is available.
This is joint work with Kostas Tsioutsiouliklis (Princeton University)
This talk represents joint research with Anna Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, and Andrew Tomkins. The talk will be self-contained.
Collaborators: Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Raymie Stata, Andrew Tomkins, Eli Upfal and Janet Wiener.
We consider an important case of the metric labeling problem, in which the metric is the truncated linear metric. This is a natural non-uniform and robust metric which arises in a number of applications, especially in vision. We give a combinatorial 4-approximation algorithm for this metric. Our algorithm is a natural local search algorithm, where the local steps are based on minimum cut computations in an appropriately constructed graph. Our method extends previous work by Boykov, Veksler and Zabih on more restricted classes of metrics.
Joint work with Eva Tardos.
Joint work with S. Muthukrishnan.
Joint work with M. Naor.
Joint work with Leslie Goldberg, Mike Paterson (Univ. of Warwick) and Mark Jerrum (Univ. of Edinburgh)
This is joint work with W. Scott Spangler and will appear in the ACM Hypertext 2000 Conference.