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.

Balanced Graph Partitioning

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 NP-Hard, 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)