Algorithms Reading Group Fall 2005

Venue : B-11
Time : 12:30-1:30
Days : Mondays.

If you would like to speak, please send e-mail to kvaradar at cs dot uiowa dot edu.

Date	Speaker	Topic
8/29/2005	Kasturi Varadarajan	Coresets for k-median and k-means; ( Paper )
9/12/2005	Sriram Pemmaraju	Strong Edge Colorings; ( Paper )
9/12/2005	Benton McCune	Price Adjustment Schemes;
9/26/2005	kevin Lillis	Robust Position-Based Routing in Wireless Ad Hoc Networks with Unstable Transmission Ranges, by Barriere, Fraigniaud, Narayanan; ( Paper )
10/03/2005	N.D. Shyamalkumar	Optimal Policies to Obtain the Most Join Results ;
10/10/2005	Shouxi Yang	Adwords and Generalized on-line matching, by Mehta, Saberi, Vazirani, and Vazirani; ( Paper )
10/24/2005	Saurav Pandit	Local Approximation Schemes for Topology Control, by Damian, Pandit, and Pemmaraju;
11/14/2005	Jarrko Kari	Survey of Reversible Cellular Automata;
11/28/2005	Sriram Pemmaraju	Strong Chromatic Number of Graphs;

Abstracts

Kasturi Varadarajan (8/29/2005)
Coresets for k-median and k-means

We will discuss a paper by Har-Peled and Kushal from the Symposium on Computational Geometry 05, entitled `Smaller coresets for k-median and k-means clustering'. The paper considers an approach, via coresets, to solve the k-means and k-median problem in fixed dimension, and shows the existence of small coresets for these problems.

Sriram Pemmaraju (9/12/2005)
Strong Edge Colorings

A strong edge coloring of a graph G is an assignment of colors to edges so that every two edges at distance at most 2 receive different colors. Two edges are at distance at most two iff either they share an endpoint, or an endpoint of one is a neighbor of an endpoint of the other. This is an old problem that has received attention recently because of its relevance to scheduling transmissions in wireless networks. I will show that the problem of computing a strong edge coloring is NP-complete even for a subclass of bipartite graphs. I will also present poly-time algorithms for some other classes of graphs.

Kevin Lillis (9/26/2005)
Robust Position-Based Routing in Wireless Ad Hoc Networks with Unstable Transmission Ranges

Several papers showed how to perform routing in ad hoc wireless networks based on the positions of the mobile hosts. However, all these protocols are likely to fall if the transmission ranges of the mobile hosts vary due to natural or man-made obstacles or weather conditions. These protocols may fall because in routing either some connections are not considered which effectively results in disconnecting the network, or the use of some connections causes livelocks. In this paper, we describe a robust routing protocol that tolerates up to roughly 40% of variation in the transmission ranges of the mobile hosts. More precisely, our protocol guarantees message delivery in a connected adhoc network whenever the ratio of the maximum transmission range to the minimum transmission range is at most sqrt(2).

N.D. Shyamalkumar (10/03/2005)
Optimal Policies to Obtain the Most Join Results

Consider two finite or infinite populations, each member of which carries a positive integer valued label. Samples are drawn without replacement. A match is said to occur between two sampled members if they are from different populations and carry the same label. The object is to sample from the two sources in an order that, if possible, maximizes the number of matches uniformly across all steps. We present a finite sample analysis and in the case of infinite population also an asymptotic analysis of this problem. While the work is motivated by a database problem the talk will be probabilistic in nature. This is a joint work with Ramon Lawrence and Ralph Russo.

Shouxi Yang (10/10/2005)
Adwords and Generalized on-line matching

Search engine companies, such as Google, Yahoo and MSN, earn revenue from businesses by displaying their ads in response to a relevant search query. The subsequent interesting problem, to assign user queries to advertisers to maximize the total revenue, is called Adwords problem, which turns out to be a generalization of the online bipartite matching problem. We are going to discuss the notion of a tradeoff revealing LP and use it to derive an algorithm achieving competitive ratio of 1-1/e for this problem.

Saurav Pandit (10/24/2005)
Local Approximation Schemes for Topology Control

In this paper, we provide a poly-log time distributed algorithm to construct an (1+\epsilon)-spanner with constant maximum degree, whose total weight is within constant factor of the weight of the minimum spanning tree. We show that our result hold for an unit-disk-graphs (UDG) as well as for quasi-UDGs which are believed to be a more realistic model of ad-hoc wireless networks.

Jarrko Kari (11/14/2005)
Survey of Reversible Cellular Automata

Reversible cellular automata (RCA) are models of massively parallel computation that preserve information. This talk is a short survey of research on reversible cellular automata over the past fourty plus years. We discuss the classic results by Hedlund, Moore and Myhill that relate injectivity, surjectivity and reversibility with each other. Then we review algorithmic questions and some results on computational universality. Finally we talk about local reversibility vs. global reversibility in cellular spaces.

Sriram Pemmaraju (11/28/2005)
Strong chromatic number of graphs

In 1992, Alon used the probabilistic method to show that the strong chromatic number of a graph with max. degree Delta is bounded above by c times Delta, where c is a constant. The constant c that falls out of Alon's proof is ridiculously large (about 100 million). In 2004, Haxell used elementary combinatorial techniques to prove an upper bound of 3 times delta - 1. I will present Haxell's proof.