Capital Area Theory Seminar: Spring 2004

Schedule

CATS will usually meet on Friday 3:00pm-4:00pm AVW 3258 but some talks may be at a different place and time.

For additional information send email to Samir Khuller.

If you want to receive announcements of upcoming talks join the theory-local mailing list.

Talks from previous semesters

• 2003 : Fall | Spring
• 2002 : Fall | Spring
• 2001 : Fall
• 2000 : Fall | Spring
• 1999 : Fall | Spring
• 1998 : Fall | Spring
• 1997 : Fall | Spring
• 1996 : Summer and Fall | Spring
• 1995 : Fall

Other cats

Combinatorial Algorithms Test Sets Collaborative Agent Technology System Computing: The Australasian Theory Symposium

Abstracts

A primal-dual 3-approximation for Facility Location

I will present a primal-dual algorithm for approximating the Facility Location problem. My talk will be based on "Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems" by Jain and Vazirani, although I will show a simpler proof of the same result.

Reference: Kamal Jain, Vijay V. Vazirani. Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. FOCS 1999.

Minimizing Congestion in General Networks

A principle task in parallel and distributed systems is to reduce the communication load in the interconnection network, as this is usually the major bottleneck for the performance of distributed applications. In this paper we introduce a framework for solving on-line problems that aim to minimize the congestion (i.e. the maximum load of a network link) in general topology networks.

We apply this framework to the problem of on-line routing of virtual circuits and to a dynamic data management problem. For both scenarios we achieve a competitive ratio of O(log^3 n) with respect to the congestion of the network links.

Our on-line algorithm for the routing problem has the remarkable property that it is oblivious, i.e., the path chosen for a virtual circuit is independent of the current network load. Oblivious routing strategies can easily be implemented in distributed environments and have thereforebeen intensively studied for certain network topologies as e.g. meshes, tori and hypercubic networks. This is the first oblivious path selection algorithm that achieves a polylogarithmiccompetitive ratio in general networks.

Reference: Harald Racke. Minimizing Congestion in General Networks. FOCS 2002.

Primal-Dual Approximation Algorithms for k-Median

The k-Median problem and the Facility Location problem have similar formulations as linear programs. This similarity can be exploited to yield a good approximation to the k-Median problem given a good approximation to the Facility Location problem.

Reference: Kamal Jain, Vijay V. Vazirani. Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. FOCS 1999.

On the costs and Benefits of Procrastination : Approximation Algorithms for stochastic Combinational Optimization Problems.

Combinatorial Optimization is often used to plan ahead, purchasing and allocating resources for demands that are not precisely known at the time of solution. This advance planning may be done because resources become very expensive to purchase or difficult to allocate at the last minute when the demands are known. So the problem here is how to approximately optimize the choice of what to purchase in advance and what to defer.

Reference: On the costs and Benefits of Procrastination : Approximation Algorithms for stochastic Combinational Optimization Problems, Nicole Immorlica, David R. Karger, Maria Minkoff and Vahab S. Mirrokni. (SODA 04)

Chain: Operator Scheduling for Memory Minimization in Data Stream Systems.

In many applications involving continuous data streams, data arrival is bursty and data rate fluctuates over time. Systems that seek to give rapid or real-time query responses in such an environment must be prepared to deal gracefully with bursts in data arrival without compromising system performance. The choice of an operator scheduleing strategy can have significant impact on the run-time memory usage. The paper presents Chain-scheduling, an operator scheduling strategy for Data Stream Systems that is near-optimal in minimizing run-time memory usage for any collection of single-stream queries invloving selections, projections, and foriegn-key joins with stored relations.

Reference: Chain: Operator Scheduling for Memory Minimization in Data Stream System. Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani (SIGMOD 03)

Unreliable Failure Detectors for Reliable Distributed Systems

We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures.

We characterise unreliable failure detectors in terms of two properties – and accuracy. We show that Consensus can be solved even with unreliable failure detectors that make an infinite number of mistakes, and determine which ones can be used to solve Consensus despite any number of crashes, and ones require a majority of correct processes. We prove that and Atomic Broadcast are reducible to each other in asynchronous systems with crash failures; thus the above results also apply to Atomic Broadcast. A companion paper shows one of the failure detectors introduced here is the weakest detect for solving Consensus.

Reference: Unreliable Failure Detectors for Reliable Distributed Systems. Tushar Deepak Chandra and Sam Toueg. Journal of the ACM, 1996.

Buffer Minimization using Max-coloring

Given a graph G=(V,E) and positive integral vertex weights w: V->N, the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C_1, C_2,..., C_k, minimize the sum of max vertex weight in a color class. Though this problem seems similar to the well-known dynamic storage allocation problem, we point out fundamental differences. We make a connection between max-coloring and on-line graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields a 10-approximation algorithm.

Reference: Buffer Minimization using Max-coloring, Sriram V. Pemmaraju, Rajiv Raman, Kasturi Varadarajan (SODA 2004)

Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs

A certifying algorithm for a decision problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of non-membership can be authenticated in O(|V|) time.

Reference: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs, by Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, and Jeremy P. Spinrad (SODA 2003)

Connectedness in r-random graphs

I'll be presenting some of Chapter 2 of Bollobas' book Random Graphs. We will be showing that almost every random graph is connected if edges appear with probability greater than (1+c)ln n / n. The goal will be to bound the probability that connectedness will occur in order that we might know the probability that a random graph of size n is connected.

How bad is selfish routing?

We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, 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 its congestion; the objective is to route traffic such that the sum of all travel times -the total latency- is minimized.In many settings, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central 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.In this article, we quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and nondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulated selfish network users may be arbitrarily larger than the minimum possible total latency; however, we prove that it is no more than the total latency incurred by optimally routing twice as much traffic.