[home] - [up]

Lectures and Colloquia during the semester

November 19, 2001

Technische Universität Berlin
Straße des 17. Juni 136, 10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Susanne Albers - Freiburg University

Some Algorithmic Problems in Large Networks

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

Diana Poensgen - Konrad-Zuse-Zentrum Berlin

News from the Online Traveling Repairman

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]