Algorithms Reading Group Spring 2005

Venue : B-11
Time : 11:30-12:30
Days : Fridays.

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

Date	Speaker	Topic
1/28/2005	Ra jiv Raman	Inapproximability results and approximation algorithms for max-coloring on trees and bipartite graphs.
2/4/2005	Ben Gum	Approximating edit distance efficiently (paper)
2/11/2005	Kasturi Varadarajan	Geometric Set Cover
2/18/2005	Ben McCune	Interior Point methods for Linear Programming
2/25/2005	Jarkko Kari	Tight linear bound on the inverse neighborhood of reversible cellular automata
3/4/2005	Sriram Pemmaraju	Max-coloring graphs that can be colored approximately
3/11/2005	Saurav Pandit	Constant-Time Distributed Dominating Set Approximation (paper)
3/18/2005	Spring Break
3/25/2005	Ra jiv Raman	How Bad is selfish routing
4/1/2005	Ben Gum	Cancelled
4/8/2005	Kasturi Varadarajan	Computing Market Equilibria
4/15/2005	Sriram Pemmaraju	Topology Control without Geometric Information
4/22/2005	Sridhar Dighe	A Near-Linear Constant-Factor Approximation for Euclidean Bipartite Matching
4/29/2005	Ben McCune	How much can taxes help in selfish routing ? paper

Seminars from previous semesters: Fall 2004, Spring 2004, Fall 2003.

Abstracts

Rajiv Raman ( 1/24/2005)
Inapproximability results and approximation algorithms for max-coloring on trees and bipartite graphs.

Given a graph G=(V,E), with positive weight function 'w' on the vertices, the max-coloring problem seeks to find a proper vertex coloring of G that minimizes the sum of the cost of color classes, where the cost of a color class is the maximum weight of a vertex in the color class.
Hence, if C_1, ... ,C_k are k color classes in a coloring, the cost of this coloring is SUM {i=1..k} max { v in C_i} w(v). We want to find C_1, ..., C_k that minimizes this cost function. The problem arises in scheduling conflicting jobs, and in resource allocation.

I will present a 7/6-approximation algorithm for max-coloring a bipartite graph, and also show a 7/6-\epsilon hardness. If time permits, I will also present results on trees. I will present an algorithm that runs in O(n^O{log n}) time and computes an optimal max-coloring, and also use this to develop a PTAS ( a (1+\epsilon)-approximation for any \epsilon > 0).
This is joint work with Sriram Pemmaraju.

Ben Gum (2/4/2005)
Approximating edit distance efficiently

by Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar

Edit distance has been extensively studied for the past several years. Nevertheless, no linear-time algorithm is known to compute the edit distance between two strings, or even to approximate it to within a modest factor. Furthermore, for various natural algorithmic problems such as low-distortion embeddings into normed spaces, approximate nearest-neighbor schemes, and sketching algorithms, known results for the edit distance are rather weak. We develop algorithms that solve gap versions of the edit distance problem: given two strings of length $n$ with the promise that their edit distance is either at most $k$ or greater than $l$, decide which of the two holds. We present two sketching algorithms for gap versions of edit distance. Our first algorithm solves the $k$ vs. $(k n)^{2/3}$ gap problem, using a constant size sketch. A more involved algorithm solves the stronger $k$ vs. $l$ gap problem, where $l$ can be as small as $O(k^2)$---still with a constant sketch---but works only for strings that are mildly ``non-repetitive''. Finally, we develop an $n^{3/7}$-approximation quasi-linear time algorithm for edit distance, improving the previous best factor of $n^{3/4}$ due to Cole and Hariharan [SIAM J. on Computing, 2002]; if the input strings are assumed to be non-repetitive, then the approximation factor can be strengthened to
$n^{1/3}$.

Kasturi Varadarajan (2/11/2005)
Geometric Set Cover

We consider problems of the following kind: Given a set of points in the plane and a set of fat triangles that cover the points, find a minimum sized subset of the triangles that cover the given points. These problems are typically NP-hard. We present polynomial time algorithms whose approximation guarantees follow from improved bounds on eps-nets. (Joint work with Ken Clarkson.)

Ben McCune (2/25/2005)
Interior Point methods for Linear Programming
The talk will present a very brief introduction to interior point methods. Specifically, I will present a primal path algorithm for Linear Programming and some motivation for it. This algorithm is due to Gonzaga (1989) and I rely on the exposition in Bertsimas and Tsitsiklis _Introduction to Linear Optimization_. This algorithm matches the best known time complexity for LP and performs well practically.

Jarkko Kari (2/25/2005)
Tight linear bound on the inverse neighborhood of reversible cellular automata
(Joint work with Eugen Czeizler)
Reversible cellular automata (RCA) are models of massively parallel computation that preserve information. They consist of an array of identical finite state machines that change their states synchronously according to a local update rule. By selecting the update rule properly the system has been made information preserving, which means that any computation process can be traced
back step-by-step using an inverse automaton. We investigate the maximum range in the array that a cell may need to see in order to determine its previous state. We provide a tight upper bound on this inverse neighborhood size in the one-dimensional case: we prove that in an RCA with n states the inverse neighborhood is not wider than n-1, when the neighborhood in the forward direction consists of two consecutive cells. Examples are known where range n-1 is needed, so the bound is tight. If the forward neighborhood consists of m consecutive cells then the same technique provides the upper bound n^(m-1)-1 for the inverse direction.

Sriram Pemmaraju (3/4/2005)
Max-coloring graphs that can be colored approximately
In this talk I'll present a 4c-approximation algorithm for max-coloring on classes of graphs for which the classical graph coloring problem has a c-approximation. Time permitting, I'll show how this approximation can be improved.

(Joint work with Rajiv Raman)

Saurav Pandit(3/10/2005)
Constant-Time Distributed Dominating Set Approximation (2003)
Fabian Kuhn, Roger Wattenhofer
Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary parameter k, our algorithm computes a dominating set of expected size O(k. #^(2/k) log #|DSOPT|) in O(k^2) rounds where each node has to send O(k^2.#) messages of size O(log #). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.

Rajiv Raman(3/25/2005)
How Bad is Selfish Routing ?
We are given a network and a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given it's congestion. The objective is to route traffic such that the sum of all travel times - the total latency is minimized.

We consider situations where there is no centralized traffic regulating authority, and in the absence of such an authority we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general, such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence this lack of regulation carries the cost of decreased network performance.

We quantify the degradation in network performance due to unregulated traffic and prove that if the latency of each edge is a linear function of it's congestion, then the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency.

Kasturi Varadarajan (4/8/2005)
Computing Market Equilibria
I will speak about some recent work of mine on the computation of market equilibria in certain economies with constant-returns-to-scale production technologies. The main result is a polynomial-time algorithm obtained by showing that the problem can be posed as a convex feasibility problem.

Sriram Pemmaraju (4/15/2005)
Topology Control without Geometric Information
A wireless network comes with nodes, but without edges. Edges are defined by each node choosing as neighbors, a subset of nodes within its transmission range. The problem of each node making a local choice of neighbors so as to induce a network that has good global properties such as symmetry, connectivity, sparsity, spanner property, etc., is the topology control problem.

Recently, several protocols have been presented for the topology control problem that make explicit use of geometric information (e.g. location of each node in space). However, geometric information can be quite unreliable and the current generation of topology control protocols are not robust to even tiny errors in this information. We propose a randomized topology control protocol that uses no geometric information, but seems to compete with the best existing topology control protocols in running time and the quality of the output produced.

This is joint work with Kevin Lillis.

Sridhar Dighe (4/22/2005)
A Near-Linear Constant-Factor Approximation for Euclidean Bipartite Matching
In the Euclidean bipartite matching problem, we are given a set R of red points and set B of blue points in R^d where |R| = |B| = n, and we want to pair up each red point with a distinct blue point so that the sum of distances between the paired points is minimized. We present an approximation algorithm that given any parameter 0 < eta < 1 runs in O(n ^(1+ eta) ) expected time and returns a matching whose expected cost is within a multiplicative factor O(log(1/eta)) of the optimal. The dimension d is considered to be a fixed constant.

AUTHOR - Pankaj K. Agarwal and Kasturi R. Varadarajan.

Note - From the given paper I will be covering only the algorithm in
which we come up with ?(1/eta) approximation. Later part is not included
in the presentation.

Ben McCune (4/29/2005)
How much can taxes help in selfish routing ?
How should network edges be priced to reduce the cost of selfish routing,
where cost is defined as the sum of user utilities (the sum of the delays
incurred and the taxes paid)? Marginal cost taxes (aka congestion or
Pigouvian taxes), which aim to minimize only the sum of delays, are only
appropriate for this goal only if taxes can be feasibly refunded to users
in a lump-sum fashion. Since exorbitant taxes can effectively delete edges
from a network, this generalizes the FOCS '01 paper on network design.