Exploring unknown environments (2007)
Albers, Susanne, Henzinger, Monika R.
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
On Nash Equilibria for a Network Creation Game (2006)
Albers, Susanne, Eilts, Stefan, Even-Dar, Eyal, Mansour, Yishay, Roditty, Liam
We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Albers, Susanne, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Flows on Few Paths: Algorithms and Lower Bounds (2004)
Martens, Maren, Skutella, Martin, Albers, Susanne, Radzik, Tomasz
In classical network flow theory, flow being sent from a source to a destination may be split into a large number of chunks traveling on different paths through the network. This effect is undesired...
Super Scalar Sample Sort (2004)
Sanders, Peter, Albers, Susanne, Radzik, Tomasz
Sample sort, a generalization of quicksort that partitions the input into many pieces, is known as the best practical comparison based sorting algorithm for distributed memory parallel computers. We...
Incremental Algorithms for Facility Location and k-Median (2004)
Fotakis, Dimitris, Albers, Susanne, Radzik, Tomasz
In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing...
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Albers, Susanne, Radzik, Tomasz
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the removal of which leaves no perfect matching in $G$. We give an explicit characterization of the minimal blockers of a...
Dynamic TCP Acknowledgement: Penalizing Long Delays (2003)
We study the problem of acknowledging a sequence of data packets that are sent across a TCP connection. Previous work on the problem has focused mostly on the objective function that minimizes the...
On Paging with Locality of Reference (2003)
Susanne Albers, Lene M. Favrholdt, Oliver Giel
Motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and...
Randomized Splay Trees: Theoretical and Experimental Results (2002)
Susanne Albers, Marek Karpinski
Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [12]. In this paper we present the first randomized variant of these trees. The new algorithm for...
Generalized Connection Caching (2000)
Susanne Albers, Lehrstuhl Informatik Ii
Cohen et al. [5] recently initiated the theoretical study of connection caching in the world-wide web. They extensively studied uniform connection caching, where the establishment cost is uniform for...
An Experimental Study of Online Scheduling Algorithms (2000)
Susanne Albers, Bianca Schroder
We present the first comprehensive experimental study of online algorithms for Graham's scheduling problem. Graham's scheduling problem is a fundamental problem in scheduling theory where a sequence...
Online Algorithms: A Study of Graph-Theoretic Concepts (2000)
. In this paper we survey results on the design and analysis of online algorithms, focusing on problems where graphs and graphtheoretic concepts have proven particularly useful in the formulation or...
Page Replacement for General Caching Problems (2000)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
A Combined BIT and TIMESTAMP Algorithm for the List Update Problem (2000)
Susanne Albers, Bernhard Von Stengel, Ralph Werchner
We present a randomized on-line algorithm for the list update problem which achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between two known...
Page Migration with Limited Local Memory Capacity (2000)
Page migration problems arise in distributed data management. The goal is to distribute a set of pages in a network of processors, each of which has its local memory, so that a sequence of memory...
Susanne Albers, Stefano Leonardi
s been applied successfully to many interesting problems. Applications In the late eighties and early nineties, three basic online problems were studied extensively, namely paging, the k-server...
Delayed Information and Action in On-Line Algorithms (1999)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...
Scheduling with Unexpected Machine Breakdowns (1999)
Susanne Albers, Gunter Schmidt
We investigate an online version of a basic scheduling problem where a set of jobs has to be scheduled on a number of identical machines so as to minimize the makespan. The job processing times are...
Page Replacement for General Caching Problems (1999)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
A Survey of Self-Organizing Data Structures (1999)
This paper surveys results in the design and analysis of self-organizing data structures for the search problem. The general search problem in pointer data structures can be phrased as follows. The...
Self-Organizing Data Structures (1999)
. We survey results on self-organizing data structures for the search problem and concentrate on two very popular structures: the unsorted linear list, and the binary search tree. For the problem of...
Exploring Unknown Environments with Obstacles (1999)
Susanne Albers, Klaus Kursawe, Sven Schuierer
We study exploration problems where a robot has to construct a complete map of an unknown environment using a path that is as short as possible. In the first problem setting we consider, a robot has...
Competitive Online Algorithms (1999)
this article we give an introduction to the theory of online algorithms and survey interesting application areas. We present important results and outline directions for future research. Introduction
On the Influence of Lookahead in Competitive Paging Algorithms (1999)
We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is on-line with strong lookahead l if it sees the present request...
Improved Parallel Integer Sorting without Concurrent Writing (1999)
Susanne Albers, Torben Hagerup
We show that n integers in the range 1 : : n can be sorted stably on an EREW PRAM using O(t) time and O(n( p log n log log n + (log n) 2 =t)) operations, for arbitrary given t log n log log n, and on...
Average-Case Analyses of First Fit and Random Fit Bin Packing (1999)
Susanne Albers, Michael Mitzenmacher
We prove that the First Fit bin packing algorithm is stable under the input distribution Ufk Gamma 2; kg for all k 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...
A Competitive Analysis of the List Update Problem with Lookahead (1999)
We consider the question of lookahead in the list update problem: What improvement can be achieved in terms of competitiveness if an on-line algorithm sees not only the present request to be served...
Minimizing Stall Time in Single and Parallel Disk Systems (1999)
Susanne Albers, Naveen Garg, Stefano Leonardi
We study integrated prefetching and caching problems following the work of Cao et. al. [3] and Kimbrel and Karlin [13]. Cao et. al. and Kimbrel and Karlin gave approximation algorithms for minimizing...
Better Bounds For Online Scheduling (1999)
. We study a classical problem in online scheduling. A sequence of jobs must be scheduled on m identical parallel machines. As each job arrives, its processing time is known. The goal is to minimize...
A Combined BIT and TIMESTAMP Algorithm for the List Update Problem (1999)
Susanne Albers, Bernhard Von Stengel, Ralph Werchner
. A simple randomized on-line algorithm for the list update problem is presented that achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between...
Scheduling with Unexpected Machine Breakdowns (1999)
Susanne Albers, Gunter Schmidt
We investigate an online version of the scheduling problem P; NCjpmtnjC max , where a set of jobs has to be scheduled on a number of identical machines so as to minimize the makespan. The job...
Delayed Information and Action in On-Line Algorithms (1999)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time-step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...
Susanne Albers, Stefano Leonardi
algorithms to obtain better competitive ratios than deterministic algorithms. BenDavid et al . [13] explored the power of randomization in online algorithms. Given a randomized online algorithm A, an...
Improved Randomized On-Line Algorithms for the List Update Problem (1999)
The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of p 3 ß 1:73. In this paper we present a new family of randomized on-line algorithms that...
New On-Line Algorithms for the Page Replication Problem (1999)
We present improved competitive on-line algorithms for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive ratio can be...
Revisiting the COUNTER Algorithms for List Update (1999)
Susanne Albers, Michael Mitzenmacher
COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook, and Sleator [7]. They showed that for any ffl ? 0, there exist COUNTER...
Page Migration with Limited Local Memory Capacity (1999)
. Most previous work on page migration assumes that each processor, in the given distributed environment, has infinite local memory capacity. In this paper we study the migration problem under the...
Exploring Unknown Environments (1999)
Susanne Albers, Monika R. Henzinger
. We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Competitive Online Algorithms (1999)
Susanne Albers, Mpi Saarbrucken
is 1.1 Basic definitions Formally, many online problems can be described as follows. An online algorithm A is presented with a request sequence oe = oe(1); oe(2); : : : ; oe(m). The algorithm A has...
Page Replacement for General Caching Problems (1999)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
Self-Organizing Data Structures (1999)
. We survey results on self-organizing data structures for the search problem and concentrate on two very popular structures: the unsorted linear list, and the binary search tree. For the problem of...
Page Migration with Limited Local Memory Capacity (1999)
. Most previous work on page migration assumes that each processor, in the given distributed environment, has infinite local memory capacity. In this paper we study the migration problem under the...
Revisiting the COUNTER Algorithms for List Update (1999)
Susanne Albers, Michael Mitzenmacher
COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook, and Sleator [7]. They showed that for any ffl ? 0, there exist COUNTER...
Exploring Unknown Environments (1999)
Susanne Albers, Monika R. Henzinger
. We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Page Replacement for General Caching Problems (1999)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
New On-Line Algorithms for the Page Replication Problem (1999)
We present improved competitive on-line algorithms for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive ratio can be...
A Combined BIT and TIMESTAMP Algorithm for the List Update Problem (1999)
Susanne Albers, Bernhard Von Stengel, Ralph Werchner
. A simple randomized on-line algorithm for the list update problem is presented that achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between...
A Competitive Analysis of the List Update Problem with Lookahead (1999)
We consider the question of lookahead in the list update problem: What improvement can be achieved in terms of competitiveness if an on-line algorithm sees not only the present request to be served...
Competitive Online Algorithms (1999)
Susanne Albers, Mpi Saarbrucken
e analysis 1.1 Basic definitions Formally, many online problems can be described as follows. An online algorithm A is presented with a request sequence oe = oe(1); oe(2); : : : ; oe(m). The algorithm...
Better Bounds For Online Scheduling (1999)
. We study a classical problem in online scheduling. A sequence of jobs must be scheduled on m identical parallel machines. As each job arrives, its processing time is known. The goal is to minimize...
Minimizing Stall Time in Single and Parallel Disk Systems (1999)
Susanne Albers, Naveen Garg, Stefano Leonardi
We study integrated prefetching and caching problems following the work of Cao et. al. [3] and Kimbrel and Karlin [13]. Cao et. al. and Kimbrel and Karlin gave approximation algorithms for minimizing...
Exploring Unknown Environments with Obstacles (1999)
Susanne Albers, Klaus Kursawe, Sven Schuierer
We study exploration problems where a robot has to construct a complete map of an unknown environment using a path that is as short as possible. In the first problem setting we consider, a robot has...
Self-Organizing Data Structures (1999)
. We survey results on self-organizing data structures for the search problem and concentrate on two very popular structures: the unsorted linear list, and the binary search tree. For the problem of...
Competitive Online Algorithms (1999)
this article we give an introduction to the theory of online algorithms and survey interesting application areas. We present important results and outline directions for future research.
Delayed Information and Action in On-Line Algorithms (1999)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time-step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...
Average Case Analyses of List Update Algorithms, with Applications to Data Compression (1999)
Susanne Albers, Michael Mitzenmacher
We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...
Page Replacement for General Caching Problems (1998)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
Page Replacement for General Caching Problems (1998)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
Page Replacement for General Caching Problems (1998)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
Page Replacement for General Caching Problems (1998)
Susanne Albers, Sanjeev Arora, Sanjeev Khanna
Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent...
Revisiting the COUNTER Algorithms for List Update (1998)
Susanne Albers, Michael Mitzenmacher
COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook and Sleator [7]. They showed that for any ffl ? 0, there exist COUNTER...
Average-Case Analysis of First Fit and Random Fit Bin Packing (1998)
Susanne Albers, Michael Mitzenmacher
We prove that the First Fit bin packing algorithm is stable under the input distribution U {k - 2, k} for all k # 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...
Average Case Analyses of List Update Algorithms, with Applications to Data Compression (1998)
Susanne Albers, Michael Mitzenmacher
We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...
Delayed Information and Action in On-Line Algorithms (1998)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...
Revisiting the COUNTER Algorithms for List Update (1998)
Susanne Albers, Michael Mitzenmacher
COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook and Sleator [7]. They showed that for any ffl ? 0, there exist COUNTER...
Delayed Information and Action in On-Line Algorithms (1998)
Susanne Albers, Moses Charikar, Michael Mitzenmacher
Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate e#ect. In many on-line problems, however, the time...
Average Case Analyses of List Update Algorithms, with Applications to Data Compression (1998)
Susanne Albers, Michael Mitzenmacher
We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...
Exploring Unknown Environments (1998)
Susanne Albers, Monika R. Henzinger
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Minimizing Stall Time in Single and Parallel Disk Systems (1998)
Susanne Albers, Naveen Garg, Stefano Leonardi
We study integrated prefetching and caching problems following the work of Cao et. al. [3] and Kimbrel and Karlin [14]. Cao et. al. and Kimbrel and Karlin gave approximation algorithms for minimizing...
Average Case Analyses of List Update Algorithms, with Applications to Data Compression (1998)
Susanne Albers, Michael Mitzenmacher
We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...
A Combined BIT and TIMESTAMP Algorithm for the List Update Problem (1998)
Susanne Albers, Bernhard Von Stengel, Ralph Werchner
. A simple randomized on-line algorithm for the list update problem is presented that achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between...
Improved Randomized On-Line Algorithms for the List Update Problem (1998)
The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of p 3 1:73. In this paper we present a new family of randomized on-line algorithms that beat...
Direct-mapped Constrained Migration Problem (1997)
The constrained migration problem arises in the memory management of large multiprocessor systems. Given a network of processors, each of which has its own local memory, the purpose of this problem...
Exploring Unknown Environments (1997)
Susanne Albers, Monika Rauch Henzinger
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Exploring Unknown Environments (1997)
Susanne Albers, Monika R. Henzinger
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Susanne Albers, Michael Mitzenmacher
We prove that the First Fit bin packing algorithm is stable under the input distribution U {k - 2, k} for all k # 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...
A Combined BIT and TIMESTAMP Algorithm for the List Update Problem (1997)
Susanne Albers, Bernhard Von Stengel, Ralph Werchner
. We present a randomized on-line algorithm for the list update problem which achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between two...
Competitive Online Algorithms (1996)
s always the running example to explain and illustrate the material. We also discussed the k-server problem, which is a very well-studied generalization of the paging problem. The second lecture was...
Direct-mapped Constrained Migration Problem (1995)
The constrained migration problem arises in the memory management of large multiprocessor systems. Given a network of processors, each of which has its own local memory, the purpose of this problem...