Papers

2004 "Balanced Graph Partitioning" with Harald Raecke,
published in the Proceeding of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Barcelona, Spain 2004

2004 "Simultaneous Source Location" with Charles Garrod, Bruce M. Maggs and Adam Meyerson,
published in the Proceeding of the 7th. International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Boston 2004

2003 "Designing Overlay Multicast Networks for Streaming" with Bruce M. Maggs, Adam Meyerson and Ramesh K. Sitaraman,
published in the Proceeding of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego 2003

2000 "Moments of Spherical Codes and Designs" with S. Boumova and P.Boyvalenkov,
published in the Proceedings of the 7th Workshop on Algebraic
and Combinatorial Coding Theory (ACCT), Bansco 2000.
In this paper we consider the problem of $(k,\nu)$balanced graph partitioning  dividing the vertices of a graph into $k$ almost equal size components (each of size less than $\nu \cdot \frac{n}{k}$) so that the capacity of edges between different components is minimized.
This problem is a natural generalization of several other problems such as minimum bisection, which is the $(2,1)$balanced partitioning problem.
We present a bicriteria polynomial time approximation algorithm with an $O(\log^2{n})$approximation for any constant $\nu>1$. For $\nu =1$ we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless $P=NP$. Previous work has only considered the $(k,\nu)$balanced partitioning problem for $\nu \geq 2$.
Full text (PDF)
Simultaneous Source Location
We consider the problem of Simultaneous Source Location  selecting locations for s
ources in a capacitated graph such that a given set of demands can be satisfied. We give an exa
ct algorithm for trees and show how this can be combined with a result of R\"{a}cke to give a s
olution with $O(\log n \log \log n)$ dilation on the capacities. On graphs of bounded tree widt
h, we show the problem is still NPHard, but we are able to give a solution with $O(1+\epsilon)
$ dilation on the capacities, or a $k+1$approximation with exact capacities (where $k$ is the
tree width).
Full text (PDF)
Designing Overlay Multicast Networks for Streaming
We present an approximation algorithm for designing a
multicast overlay network. The algorithm finds a solution that
satisfies capacity and reliability constraints to within a constant
factor of optimal, and cost to within a logarithmic factor.
Full text (PDF)
Moments of Spherical Codes and Designs
We introduce and investigate certain invariants of spherical codes which
turn to be useful in dealing with linear programming bounds for spherical
codes and designs.
Full text (PDF)