[home] - [up] |

Lectures and Colloquia during the semester

Technische Universität Berlin

Straße des 17. Juni 136, 10623 Berlin

Math building - Room MA 042 - map -

*Abstract: *
We study caching problems that arise in large networks such as the
world-wide web. In the *connection caching* problem, we
have to maintain a set of persistent TCP connections. We consider
a general setting where connections may incur varying establishment
costs. We develop online algorithms that achieve an optimal competitive
ratio and, in particular, present strategies that use different amounts of
extra communication among network nodes while maintaining open connections.
In the *TCP acknowledgment problem* we have to acknowledge
dynamically the arrival of data segments that are being sent over
a TCP connection. The goal is to minimize the total number of
acknowledgments sent and the delays incurred for the segments.
The consider objective functions that penalize long delays
and develop online algorithms that achieve an optimal competitiveness.
In the *document caching* problem, we have to maintain local
user caches containing documents from the web. We develop polynomial
time constant factor approximation algorithms that use a small amount
of extra space in cache. Our solutions are based on integer linear
program formulations of web caching problems. (Joint work with
S. Arora and S. Khanna.)

** Colloquium - 16:00**

*Abstract: *
In the traveling repairman problem (TRP), a tour must be found through
every one of a set of points (cities) in some metric space such that
the weighted sum of completion times of the cities is minimized.
Given a tour, the completion time of a city is the time traveled on
the tour before the city is reached. In the online traveling repairman
problem OLTRP requests for visits to cities arrive online while the
repairman is traveling. We analyze the performance of algorithms for
the online problem using competitive analysis, where the cost of an
online algorithm is compared to that of an optimal offline algorithm.

Feuerstein and Stougie developed a *9*-competitive algorithm for the
OLTRP on the real line. In this paper we show how to use techniques
from online-scheduling to obtain a *6*-competitive deterministic
algorithm for the OLTRP on any metric space. We also present a
randomized algorithm with competitive ratio of *3/ln 2 < 4.3281* against
an oblivious adversary. Our results extend to the "dial-a-ride"
generalization L-OLDARP of the OLTRP, where objects have to be picked
up and delivered by a server.

We supplement the deterministic lower bounds presented by Feuerstein
and Stougie with lower bounds on the competitive ratio of any
randomized algorithm against an oblivious adversary. Our lower bounds
are *(ln 16 +1)/(ln 16 -1) > 2.1282* for the L-OLDARP on the line,
*(4 e-5)/(2 e -3) > 2.41041* for the L-OLDARP on general metric spaces,
*2* for the OLTRP on the line, and *7/3* for the OLTRP on general metric
spaces.

This is joint work with Sven O. Krumke, Willem de Paepe, and Leen Stougie.

[home] - [up] - [top]