.	Capital Area Theory Seminar: Fall 2005

Schedule

We will usually meet Friday at 1:00 pm in 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

• 2005 : Spring
• 2004 : Fall | Spring
• 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

Approximation Algorithms for Scheduling on Multiple Machines

ABSTRACT:

We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. We obtain the following applications for the general setting of unrelated parallel machines:

1. A bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria (3/2 and 2, respectively)

2. Better-than-two approximation guarantees for scheduling under the Lp norm for all 1 < p < infinity, improving on the 2-approximation algorithms of Azar & Epstein

Reference: Approximation Algorithms for Scheduling on Multiple Machines, to appear in FOCS 2005.

Randomized Rumor Spreading

Srinivas R. Kashyap

ABSTRACT:

The paper investigates whether a large communication overhead (standard rumor spreading algorithms use O(n ln n) transmissions) is inherent to epidemic algorithms. On the positive side, it shows that the communication overhead can be reduced significantly. It gives an algorithm using only O(n ln ln n) transmissions and O(ln n) rounds. In addition, it proves the robustness of this algorithm. On the negative side, it shows that any address-oblivious algorithm needs to send /spl Omega/(n ln ln n) messages for each rumor, regardless of the number of rounds. Furthermore, it gives a general lower bound showing that time and communication optimality cannot be achieved simultaneously using random phone calls, i.e. every algorithm that distributes a rumor in O(ln n) rounds needs /spl omega/(n) transmissions.

Reference: Randomized Rumor Spreading, FOCS 2000, Richard Karp, Christian Schindelhauer, Scott Shenker, Berthold Vocking.

Approximation Algorithms for Traveling Salesman Path Problems

Fumei Lam

ABSTRACT:

In the Traveling Salesman Path Problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination visiting all cities exactly once. The problem is a generalization of the Traveling Salesman Problem with many important applications.

We'll survey approximation algorithms for this problem and present properties of the polytope corresponding to a linear programming relaxation. We consider the set of traveling salesman path perfect graphs, graphs for which the convex hull of incidence vectors of traveling salesman paths can be described by linear inequalities. We show such graphs have a description by way of forbidden minors and also characterize them constructively. We extend these results to relate the underlying graph structure to the integrality gap of the corresponding fractional path polyhedron.

(Joint work with Michel Goemans, Alantha Newman, and Santosh Vempala.)
 

Weighted Popular Matchings

Julian Mestre

ABSTRACT:

We study the problem of assigning applicants to jobs. Applicants have a priority or weight and provide a preference list ranking the jobs. Our ultimate goal is to produce a "good" assignment or matching between applicants and jobs.

A matching M is said to be weighted popular if there no matching R such that the "weighted majority" of the applicants prefer R over M. This is a generalization of popular matchings which were recently studied in a paper by Abraham et al. [SODA 2005]

Surprisingly, the problem can be solved in O(n+m) time for the case of strict preferences (an applicant is never indifferent among two jobs) and O(\sqrt{n} m) in general.
 

Approximation Algorithms for Broadcast Scheduling

Nikhil Bansal

ABSTRACT:

We consider the following well-studied model for broadcast scheduling. There are n pages at a broadcast server, and at each time slot the server receives several requests for these pages. The server can transmit exactly one page per time slot, and once a page is transmitted, it satisfies all the requests waiting for that page. The goal is to find a broadcast schedule that minimizes the average waiting time of requests.

I will describe an algorithm with a poly-logarithmic approximation ratio for this problem. This is joint work with Don Coppersmith and Maxim Sviridenko.
 

Interference-aware Cross-layer Algoithms for Wireless Networks

Srinivasan Parthasarathy

ABSTRACT:

Interference imposes fundamental limits on the capacity of wireless networks. Recent measurement studies have shown the need for wireless communication protocols with a significant interaction across different layers of the protocol stack, in order to effectively deal with performance problems posed by interference. In this talk, I will present techniques for designing provably-good interference-aware algorithms for wireless networks. Specifically, I will present:

1. Provably-good algorithms for computing the throughput capacity of a given wireless network of arbitrary topology.

2.  Provably-good routing and scheduling algorithms, whose *joint* performance is guaranteed to be close to the network capacity.

The algorithmic insights I present can be applied to other optimization problems such as delay-minization in wireless networks, generalized to many models of wireless interference, and constitute a unified analytical framework for cross-layer optimization in wireless networks.
 

Jitter Regulation for Multiple Streams

Maryam Farboodi

ABSTRACT:

For widely-used interactive communication, it is essential that traffic is kept as smooth as possible; the smoothness of a traffic is typically captured by its delay jitter, i.e., the difference between the maximal and minimal end-to-end delays. The task of minimizing the jitter is done by jitter regulators that use a limited-size buffer in order to shape the traffic. In many real-life situations regulators must handle multiple streams simultaneously and provide low jitter on each of them separately.

This paper investigates the problem of minimizing the jitter in such an environment, using a fixed-size buffer and specifically, the tradeoff between the buffer size available at the regulator and the optimal jitter attainable using such a buffer. The paper shows that the offline problem can be solved in polynomial time, by a time-efficient algorithm which produces an optimal schedule. It also advices an online algorithm at a cost of multiplying the buffer size linearly by the number of streams; and finally it shows that such a resource augmentation is essential up to a factor of 2 (but not number of streams).
 

Boosted Sampling: Approximation Algorithms for Stochastic Optimization

Azarakhsh Malekian

ABSTRACT:

Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. For example, in the steiner tree problem, edges must be chosen to connect terminals (clients); in vertex cover, vertices must be chosen to cover edges; in facility location, facilities must be chosen and demand vertices connected to these chosen facilities. we consider a stochastic vesion of such a problem where the solution is constructed in two stages: before the actual requirements materialize, we can choose elements in a first stage, the actual requirements are then revealed, drawn from a pre-specified probability distribution $\Pi$.; thereupon, some more elements may be chosen to obtain a feasible solution for the actual requirements. However, in this second stage, choosing an element is costlier by a factor of $\delta > 1$. The goal is to minimize the first stage cost plus the expected second stage cost. We give a general yet simple technique to adapt approximation algorithms for several deterministic problems to their stochastic versions via the following method. -First stage: Draw $\delta$ independent sets of clients from the distribution $\Pi$ and apply the approximation algorithm to construct a feasible solution for the union of these sets. -Second stage: Since the actual requirements have now been revealed, augment the first-stage solution to be feasible for these requirements.

We use framework to derive constant factor approximations for stochastic versions of Vertex Cover, Steiner Tree and uncapacittated Facility Location for arbitrary distributions $\Pi$ in one fell swoop"

Reference: Anupam Gupta, Martin Pal, R Ravi, Amitabh Sinha. Boosted Sampling: Approximation Algorithms for Stochastic Optimization. STOC 2004.

Name Independent Routing for Growth Bounded Networks

Ruggero Morselli

ABSTRACT:

A weighted undirected network is $\Delta$ growth-bounded if the number of nodes at distance $2r$ around any given node is at most $\Delta$ times the number of nodes at distance $r$ around the node. Given a weighted undirected network with arbitrary node names and $\epsilon >0$, we present a routing scheme that routes along paths of stretch $1+\epsilon$ and uses with high probability only $O( (1/\epsilon)^{O(\log \Delta)} \log^5 n )$ bit routing tables per node.

Reference: Abraham, Malkhi, "Name Independent Routing for Growth Bounded Networks", SPAA 2005. http://portal.acm.org/citation.cfm?id=1073970.1073978

Query Incentive Networks

Mikhail Kobyakov

ABSTRACT:

The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated new interest in understanding networks of interacting agents as economic systems. Here we formulate a model for query incentive networks, motivated by such systems: users seeking information or services can pose queries, together with incentives for answering them, that are propagated along paths in the network. This type of information-seeking process can be formulated as a game among the nodes in the network, and this game has a natural Nash equilibrium. In such systems, it is a fundamental question to understand how much incentive is needed in order
for a node to achieve a reasonable probability of extracting an answer to a query from the network. We study the size of query incentives as a function both of the rarity of the answer and the structure of the underlying network. This leads to natural questions related to strategic behavior in branching processes. Whereas the classically studied criticality of branching processes is centered around the region where the branching parameter is 1, we show in contrast that strategic interaction in incentive propagation exhibits critical behavior when the branching parameter is 2.

Reference: J. Kleinberg, P. Raghavan. Query Incentive Networks. http://www.cs.cornell.edu/home/kleinber/focs05-qin.pdf Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.