|
Capital Area Theory Seminar: Fall 2003 |
The Capital Area Theory Symposia is an UMIACS sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department.
CATS will usually meet on Friday 2:00pm-3:00pm CSIC 3117 but some talks may be at a different place and time. Abstracts are available.
Consider a synchronous network of processors, modeled by directed or undirected graph G = (V,E), in which on each round every processor is allowed to choose one of its neighbors and to send him a message. Given a processor s in V, and a subset T of processors, the telephone multicast problem requires to compute the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of T. The particular case T = V is called telephone broadcast problem.These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the undirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the directed variants of these problems is an open problem. We devise a combinatorial logarithmic approximation algorithm for these problems, that applies also for the directed broadcast problem. Our algorithm has significantly smaller running time, and seems to reveal more information about the combinatorial structure of the solution, than the previous algorithms, that are based on linear programming. We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. We show that there exists a constant c so that it is not possible to give better than $c\sqrt(logn)$ ratio approximation for the directed telephone broadcast problem unless $NP \subseteq DTIME(n^O(logn)))$.
A copy of this paper is available here .
Unsupervised clustering is a fundamental building block in numerous image processing applications. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method~\cite{ToG74}. The algorithm is given a set of $n$ data points in $d$-dimensional space, an integer $k$ indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute the coordinates of a set of cluster centers in $d$-space, such that those centers minimize the mean squared distance from each data point to its nearest center. This clustering algorithm is similar to another well-known clustering method, called $k$-means. One significant feature of ISOCLUS over $k$-means is that the actual number of clusters reported might be fewer or more than the number supplied as part of the input. The algorithm uses different heuristics to determine whether to merge or split clusters. As ISOCLUS can run very slowly, particularly on large data sets, there has been a growing interest in the remote sensing community in computing it efficiently.
We have developed a faster implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the $k$-means algorithm of Kanungo, et al.\cite{KMN02}. They showed that, by using a kd-tree data structure for storing the data, it is possible to reduce the running time of $k$-means. We have adapted this method for the ISOCLUS algorithm, and we show that it is possible to achieve essentially the same results as ISOCLUS on large data sets, but with significantly lower running times. This adaptation involves computing a number of cluster statistics that are needed for ISOCLUS but not for $k$-means.
Reference:
Nargess Memarsadeghi, David. M. Mount, Nathan. S. Netanyahu, and Jacqueline. Le Moigne, "A Fast Implementation of the ISOCLUS Algorithm", International Geoscience and Remote Sensing Symposium (IGARSS'03), Toulouse, France, July 21-25, 2003.
We investigate cost-sharing algorithms for multicast transmissions. Economic considerations point to two distinct mechanisms, marginal costs and Shapley value, as the two solutions most appropriate in this context. We prove that the former has a natural algorithm that uses only two messages per link of the multicast tree, while we give evidence that the latter requires a quadratic total number of messages. We also show that the welfare value achieved by an optimal multicast tree is NP-hard to approximate within any constant factor, even for bounded-degree networks. The lower bound proof for the Shapley value uses a novel algebraic technique for bounding from below the number of messages exchanged in a distributed computation; this technique may prove useful in other contexts as well.
Reference:
Joan Feigenbaum, Christos Papadimitriou, Scott Shenker. "Sharing the Cost of Multicast Transmissions", Journal of Computer and System Sciences, 2000.
A copy of the paper is available here .
More readings on the topic of Distributed Algorithmic Mechanism Design, by the same authors:
Joan Feigenbaum, Scott Shenker. "Distributed Algorithmic Mechanism Design: Recent Results and Future Directions".
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami. "A BGP-based Mechanism for Lowest-Cost Routing". Proceedings of the 2002 ACM Symposium on Principles of Distributed Computing.
Supporting fast restoration for general mesh topologies with minimal network over build is a technically challenging problem. Traditionally, ring based SONET networks have offered 50ms restoration at the cost of requiring 100% over-build. Recently, fast (local) reroute has gained momentum in the context of MPLS networks. Fast reroute, when combined with pre-provisioning of protection capacities and bypass tunnels, comes close to providing fast restoration for mesh networks, Pre-provisioning has the additional advantage of greatly simplifying network routing and signaling. Thus even for protected connections, online routing can now be oblivious to the offered protection, and only involve single shortest path computations.
We are interested in the problem of reserving the least amount of the network capacity for protection, while guaranteeing fast restoration to all the supported connections, with the constraint that the maximum amount of protection one can put on a link is limited by the amount of existing traffic on that link. Note that every link is protected by a single backup path. We show that the problem is NP-complete, and we present efficient approximation algorithms for the problem. The solution output by our algorithm is guaranteed to use at most twice the protection capacity, compared to any optimal solution. In addition, the total amount of protection capacity reserved by these algorithms is just a small fraction of the amount reserved by existing ring based schemes (e.g. SONET), especially on dense networks. The presented algorithms are computationally efficient, and can even be implemented on the network elements. Some simulation results will be presented as well.
This is joint work with Randeep Bhatia and Mansoor Alicherry, done while the speaker was a summer intern in the High-Speed Networks Research Department, Networking Research Laboratory, Bell Labs, NJ.
In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion (log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.
A copy of the paper could be found here
I'll review some classical results about the Stable Marriage Problem. In the simplest form of the problem we have n men and n women. Each man has an ordered-ranking preference list of all the women, every woman also has a preference list for the men. A marriage is a perfect matching of men and women. A matching is unstable if there are a man and a woman which are not matched and would rather be together than with their current partner in the matching. Our goal is to find a stable matching given the preference lists for every man and woman.
Reference: "The Stable Marriage Problem" (Dan Gusfied and Robert Irving), MIT Press, 1989.
The tools of information theory are often useful in developing useful bounds in computer science and (extremal) combinatorics. I will start from scratch, and present some useful applications along these lines. My two talks will mostly be based upon Jaikumar Radhakrishnan's survey article on "Entropy and Counting", available from www.tcs.tifr.res.in/~jaikumar/mypage.html . While information-theoretic methods have many different applications in computer science and combinatorics, we will focus on the (rich) counting-type applications from this article.
Consider the following puzzle. We are given n distinct points in 3D; let n1, n2, and n3 be the number of *distinct* projections of these points on the x-y plane, y-z plane, and x-z plane respectively. It is easy to see that the maximum value of n1 * n2 * n3 is n^3, and that n1 * n2 * n3 = n^2 is possible; we will give a short proof using entropy that n1 * n2 * n3 >= n^2. This puzzle is a special case of a very useful result due to Shearer.
No background in information theory will be assumed.