Algorithms
Reading Group Spring 2006
Venue : B-13
Time : 11:30-12:30
Days : Thursdays.
If you would like to speak, please send e-mail to rraman at cs dot
uiowa dot edu.
Seminars from previous semesters:
Fall
2005,
Spring
2005,
Fall
2004,
Spring
2004, Fall
2003.
Abstracts
Rajiv Raman (1/31/2006)
Min-wise independent permutations.
Given a set [n] = {0,1,...,n-1}, a set of permutations F of [n]
is said to be min-wise independent if for any subset X of [n], and a
permutation chosen randomly from F, each element of X has equal
probability of becoming the minimum element under this permutation.
I will prove some upper and lower bound results on the size of
min-wise independent families and for some relaxations of the
min-wise independence concept. I will also describe applications
of min-wise independent permutations in document clustering and
in finding dense subgraphs of large graphs.
1. "Min-wise independent permutations", A.Z.Broder, M.Charikar, A.M.Frieze and
M.Mitzenmacher, JCSS (60) (2000).
2. "Discovering large dense subgraphs in massive graphs", D.Gibson, R.Kumar.
A.Tomkins, VLDB 2005.
Kasturi Varadarajan (2/9/2006)
Online algorithms for Metric Minimum Bipartite Matching.
In this talk, we will discuss the online metric minimum
bipartite matching problem, following the paper `Randomized
Online Algorithms for Minimum Metric Bipartite Matching'
by Meyerson, Nanavati, and Poplawski in SODA 06.
Suppose there is a metric space in which k points are specified
as red in advance. Blue points arrive one by one, and as
soon as a blue point arrives, it has to be matched to a
red point. No red point can serve more than one blue point.
After k blue points have arrived, we compare the cost of
the perfect matching computed by our algorithm to the cost
of the optimal perfect matching (For instance, this can
be computed by an algorithm that knows all the red and blue points
before computing the matching). We will discuss how well some
matching algorithms perform under this measure.
The paper can be accessed
here.
Imran Pirwani(2/16/2006)
Virtual Coordinates for adhoc sensor networks.
In many applications of wireless ad hoc and sensor networks, position-
awareness is of great importance. Often, as in the case of geometric
routing,it is sufficient to have virtual coordinates, rather than real coordinates.
In this paper, we address the problem of obtaining virtual coordinates based on
connectivity information. In particular, we propose the first approximation
algorithm for this problem and discuss implementational aspects.
In the talk, I will be focusing on finding distance information that is
subsequently used to arrive at an embedding in a plane.
The paper can be accessed
here.
Ben McCune (2/23/2006)
An Application of Game Theoretic Techniques to Cryptography
This paper provides an application of game theoretic techniques to the
analysis of a class of multiparty cryptographic protocols for secret bit
exchange.
The paper can be accessed
here.
Rajiv Raman(3/2/2006)
Distributions on level-sets with applications to approximation algorithms
For vectors x in {0,1}^t, the weight of x is the number of 1's in it. Let
Let W_k(t) denote the set of elements from {0,1}^t with weight equal to k
and let [s] denote the set {1,2, .., , s}. Consider any sequence
P = (p_1, ..., p_t) of t reals such that each p_i \in [0,1] and such that
\sum p_i is an integer. Each P defines a distribution D(t;P) defined to be
any distribution on {0,1}^t such that if l= \sum p_i and (X_1, ..., X_t)
denotes a vector sampled from D(t;P) then the following hold :
1. for all i, Pr[X_i = 1] = p_i
2. Pr[|{i : X_i = 1}| = l] = 1
3. some negative correlation properties hold for all S \subset [t].
Pr[ X_i = 0] <= Pr[X_i = 0] for all X_i in S, and
Pr[ X_i = 1] <= Pr[X_i = 1] for all X_i in S.
I'll present proof of existance of such distributions and a
linear-time algorithm to sample from these distributions and describe some
applications to approximation algorithms.
The paper can be accessed
here.
Sriram Pemmaraju(3/9/2006)
Labeling schemes for tree representations
We are given a graph G = (V, E) and a labeling of edges incident
on each vertex. Specifically, for each vertex v, the edges incident
on v are labeled 0, 1,..., degree(v)-1 in some order. The problem
is to compute a spanning tree T of G with compact labeling. There
are different ways of defining the labeling cost of a spanning tree.
In this talk I will define a couple of measures of labeling cost
and present bounds on labeling cost and algorithms for computing
spanning trees with minimum labeling cost.
This paper is from the paper Labeling Schemes
for Tree Representations,
R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, and D. Peleg,
IWDC 2005.
P.S. For one of the labeling cost measures, the authors conjecture
that for any n-vertex graph and any given edge labeling, there is
a spanning tree with labeling cost O(n). The authors have shown the
existence of a spanning tree with labeling cost O(nloglogn). My hope
is that some of the students in the audience will be able to close this
gap.