Competitive Online Approximation of the (2004)
Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
How e#ciently can we search an unknown environment for a goal in unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for general...
Kayles on the Way to the Stars (2004)
We present several new results on the impartial two-person game Kayles. The original version is played on a row of pins (kayles").
Tight Bounds on Maximal and Maximum Matchings (2004)
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the...
Online Maintenance of k-Medians and k-Covers (2004)
Rudolf Fleischer, Mordecai J. Golin, Zhang Yan
The standard dynamic programming solution to finding k- medians on a line with n nodes requires O(kn ) time. Dynamic programming speed-up techniques, e.g., use of the quadrangle inequality or...
Evaluating the Educational Impact of Visualization (2004)
U Wisconsin Oshkosh, Jay Anderson, Stephen Cooper, Wanda Dann, Rudolf Fleischer, Boris Koldehofe, ...
The educational impact of visualization depends not only on how well students learn when they use it, but also on how widely it is used by instructors. Instructors believe that visualization helps...
Fun-Sort --- Or the Chaos of Unordered (2004)
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n log n). If n...
Competitive Search Ratio of Graphs and Polygons (2004)
Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
We consider the problem of searching for a goal in an unknown environment, which may be a graph or a polygonal environment. The search ratio is the worst-case ratio before the goal is found while...
The LEDA class real number - extended version (2004)
Funke,Stefan, Mehlhorn,Kurt, Schmitt,Susanne, Burnikel,Christoph, Fleischer,Rudolf, Schirra,Stefan
Polynomial deterministic rendezvous in arbitrary graphs (2004)
Kowalski, Dariusz, Pelc, Andrzej, Fleischer, Rudolf, Trippen, Gerhard
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Fleischer, Rudolf, ...
The LEDA class real number - extended version (2004)
Funke, Stefan, Mehlhorn, Kurt, Schmitt, Susanne, Burnikel, Christoph, Fleischer, Rudolf, Schirra, Stefan
Erik D. Demaine, Rudolf Fleischer, Aviezri S. Fraenkel, Richard J. Nowakowski
where the Previous player has no good move and an one where the Next player has a winning move. The end positions are P-positions and recursively, a position is an if the player to move can move to a...
Traveling Salesmen in the Presence of Competition (2003)
Sandor P. Fekete, Rudolf Fleischer, Aviezri Fraenkel, Matthias Schmitt
We propose the Competing Salesmen Problem" (CSP), a 2-player competitive version of the classical Traveling Salesman Problem. This problem arises when considering two competing salesmen instead of...
Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness (2003)
Rudolf Fleischer, Hisashi Koga
In current networks, packet losses can occur if routers do not provide su#ciently large bu#ers. This paper studies how many bu#ers should be provided in a router to eliminate packet losses. We assume...
Finding Optimal Paths in MREP Routing (2003)
Rudolf Fleischer, Mordecai Golin, Chin-tau Lea, Steven Wong
Maximum Residual Energy Path (MREP) routing has been shown an e#ective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the...
New Results for Online Page Replication (2003)
We study the online page replication problem. We present a new randomized online algorithm for rings which is 2.37297-competitive, improving the best previous result of 3.16396. We also show that no...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Fun-Sort --- Or the Chaos of Unordered (2003)
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n log n). If n...
The Algorithm Animation Repository (2003)
Pierluigi Crescenzi, Nils Faltin, Rudolf Fleischer, Christopher Hundhausen, Stefan N Aher, Guido R Oling, ...
Introduction As researchers in theoretical or practical computer science, we are used to publishing our results in form of research papers that appear in conference proceedings or journals. Journals...
Traveling Salesmen in the Presence of Competition (2002)
Fekete, Sandor P., Fleischer, Rudolf, Fraenkel, Aviezri, Schmitt, Matthias
We propose the ``Competing Salesmen Problem'' (CSP), a 2-player competitive version of the classical Traveling Salesman Problem. This problem arises when considering two competing salesmen instead of...
Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Solitaire Clobber Erik D. Demaine (2002)
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Clobber is a new two-player board game. In this paper, we introduce the 1-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Exploring the Role of Visualization and Engagement in (2002)
Vicki Almstrum, Wanda Dann, Rudolf Fleischer, Chris Hundhausen, Ari Korhonen, Lauri Malmi, ...
Visualization technology can be used to graphically illustrate various concepts in computer science. We argue that such technology, no matter how well it is designed, is of little educational value...
Exploring the Role of Visualization and Engagement in Computer Science Education (2002)
Vicki Almstrum, Wanda Dann, Rudolf Fleischer, Chris Hundhausen, Ari Korhonen, Lauri Malmi, ...
Visualization technology can be used to graphically illustrate various concepts in computer science. We argue that such technology, no matter how well it is designed, is of little educational value...
Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Demaine, Erik D., Demaine, Martin L., Fleischer, Rudolf
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Clobber is a new two-player board game. In this paper, we introduce the oneplayer variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Xiangqi and Combinatorial Game Theory (2002)
Rudolf Fleischer, Samee Ullah Khan
We explore whether combinatorial game theory (CGT) is suitable for analyzing endgame positions in Xiangqi (Chinese Chess). We discover some of the game values that can also be found in the analysis...
Optimal Robot Localization in Trees (2002)
Rudolf Fleischer, Kathleen Romanik, Sven Schuierer
The problem of localization, that is, of a robot finding its position on a map, is an important task for autonomous mobile robots. It has applications in numerous areas of robotics ranging from...
Using Finite Experiments to Study Asymptotic Performance (2002)
McGeoch,Catherine, Sanders,Peter, Fleischer,Rudolf, Cohen,Paul R., Precup,Doina
Algorithm Engineering for Parallel Computation (2002)
Bader, David, Moret, Bernard, Sanders, Peter, Fleischer, Rudolf, Moret, Bernard, Meineche Schmidt, Erik
The emerging discipline of algorithm engineering has primarily focussed on transforming pencil-and-paper sequential algorithms into robust, efficient, well tested, and easily used implementations. As...
Using Finite Experiments to Study Asymptotic Performance (2002)
McGeoch, Catherine, Sanders, Peter, Fleischer, Rudolf, Cohen, Paul R., Precup, Doina, Fleischer, Rudolf, ...
Presenting Data from Experiments in Algorithmics (2002)
Sanders, Peter, Fleischer, Rudolf, Moret, Bernard, Meineche Schmidt, Erik
Algorithmic experiments yield large amounts of data that depends on many parameters. This paper collects a number of rules for presenting this data in concise, meaningful, understandable graphs that...
Algorithm Animation for Teaching (2001)
We give an overview of rules and techniques to create a good algorithm animation, with emphasis on animations that would be used when teaching algorithms. In this context, we propose that animations...
Tight Bounds on Maximal and Maximum Matchings (2001)
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
In this paper, we study bounds on maximal and maximum matchings in special graph classes, specically triangulated graphs and graphs with bounded maximum degree. For each class, we give a lower bound...
Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang
While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
Tight Bounds on Maximal and Maximum Matchings (2001)
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
. In this paper, we study bounds on maximal and maximum matchings in special graph classes, specifically triangulated graphs and graphs with bounded maximum degree. For each class, we give a lower...
Cenek Timothy, M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, ...
While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
The Complexity of Clickomania (2001)
Biedl, Therese C., Demaine, Erik D., Demaine, Martin L., Fleischer, Rudolf, Jacobsen, Lars, Munro, J. Ian
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
Optimal Robot Localization in Trees (2001)
Rudolf Fleischer, Kathleen Romanik, Sven Schuierer
this paper we present a new strategy LPS (Localize-by-Placement-Separation) for a robot to find its position on a map, where the map is represented as a geometric tree of bounded degree. Our strategy...
The Complexity of Clickomania (2001)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
Asymptotic Complexity from Experiments? - A Case Study for Randomized Algorithms (2001)
Peter Sanders, Rudolf Fleischer, Max Planck, Insitut Informatik
In the analysis of algorithms we are usually interested in obtaining closed form expressions for their complexity, or at least asymptotic expressions in O(Delta)-notation. Unfortunately, there are...
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, J. Ian Munro
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
Graph Drawing and its Applications (2001)
Rudolf Fleischer, Colin Hirsch
Introduction Graph drawing has emerged in recent years as a very lively area in computer science. We would like to explain in this chapter why this happened and why graph drawing is an important...
On the Bahncard Problem (2000)
In this paper, we generalize the Ski-Rental Problem to the Bahncard Problem which is an online problem of practical relevance for all travelers. The Bahncard is a railway pass of the Deutsche...
Online Scheduling Revisited (2000)
. We present a new online algorithm, MR, for non-preemptive scheduling of jobs with known processing times on m identical machines which beats the best previous algorithm for m 64. For m ! 1 its...
Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, L. Demaine, Rudolf Fleischer, ...
. While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
New Results for Online Page Replication (2000)
. We study the online page replication problem. We present a new randomized algorithm for rings which is 2.37297-competitive, improving the best previous result of 3.16396. We also show that no...
Online Scheduling Revisited (2000)
Rudolf Fleischer, Michaela Wahl
. We present a new online algorithm, MR, for non-preemptive scheduling of jobs with known processing times on m identical machines which beats the best previous algorithm for m 64. For m ! 1 its...
New Results for Online Page Replication (2000)
Rudolf Fleischer, Steve Seiden
. We study the online page replication problem. We present a new randomized algorithm for rings which is 2.37297-competitive, improving the best previous result of 3.16396. We also show that no...
Online Routing in Convex Subdivisions (2000)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
New Results for Online Page Replication (2000)
Rudolf Fleischer, Steve Seiden
We study the online page replication problem. We present a new randomized algorithm for rings which is 2.37297-competitive, improving the best previous result of 3.16396. We also show that no...
Optimal Robot Localization in Trees (2000)
This video shows the problem of localization. A robot has to find its position on a map, in our case a geometric tree of bounded degree. The strategy LPS (Localize-by-PlacementSeparation) is known to...
Page Replication - Variations on a Theme (1999)
Rudolf Fleischer, Steve Seiden
. We study the online page replication problem. We present a new randomized algorithm for rings which is 2.37297-competitive, improving the best previous result of 3.16395. We also show that no...
Gautam Das, Rudolf Fleischer, Dimitris Gunopulos, Juha Karkkainen
. Given two words, text T of length n and episode P of length m, the episode matching problem is to find all minimal length substrings of text T that contain episode P as a subsequence. The...
FUN with Implementing Algorithms (1998)
. In this paper, I would like to argue -- based on my personal programming experience -- that implementing algorithms is FUN. Moreover, it can lead to a better understanding of the problem to be...
FUN with Implementing Algorithms (1998)
. In this paper, I would like to argue -- based on my personal programming experience -- that implementing algorithms is FUN. Moreover, it can lead to a better understanding of the problem to be...
On the Bahncard Problem (1997)
. In this paper, we generalize the Ski-Rental Problem to the Bahncard Problem which is an online problem of practical relevance for all travelers. The Bahncard is a railway pass of the Deutsche...
On the Bahncard Problem (1997)
. In this paper, we generalize the Ski-Rental Problem to the Bahncard Problem which is an online problem of practical relevance for all travelers. The Bahncard is a railway pass of the Deutsche...
Gautam Das, Rudolf Fleischer, Dimitris Gunopulos, Juha Karkkainen
. Given two words, text T of length n and episode P of length m, the episode matching problem is to find all minimal length substrings of text T that contain episode P as a subsequence. The...
Gautam Das, Rudolf Fleischer, Dimitris Gunopulos, Juha Karkkainen
. Given two words, text T of length n and episode P of length m, the episode matching problem is to find all minimal length substrings of text T that contain episode P as a subsequence. The...
Gautam Das, Rudolf Fleischer, Dimitris Gunopulos, Juha Karkkainen
. Given two words, text T of length n and episode P of length m, the episode matching problem is to find all minimal length substrings of text T that contain episode P as a subsequence. The...
Gautam Das, Rudolf Fleischer, Leszek Gasieniec, Dimitris Gunopulos, Juha Karkkainen
. Given two words, text T of length n and episode P of length m, the episode matching problem is to find all minimal length substrings of text T that contain episode P as a subsequence. The...
A Simple Balanced Search Tree With O(1) Worst-Case Update Time (1996)
In this paper we show how a slight modification of (a; b)-trees allows us to perform member and neighbor queries in O(log n) time and updates in O(1) worst-case time (once the position of the...
Matching Nuts and Bolts Faster (1995)
Phillip G. Bradford, Rudolf Fleischer
. The problem of matching nuts and bolts is the following : Given a collection of n nuts of distinct sizes and n bolts such that there is a oneto -one correspondence between the nuts and the bolts,...
Peter Damaschke (hagen, Uwe Schwiegelshohn (dortmund, John J. Turek, Joel L. Wolf, ...
: Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraph G is an interval order iff its (undirected) complement is...
Asymptotic Complexity from Experiments? - A Case Study for Randomized Algorithms (1970)
Peter Sanders, Rudolf Fleischer, Max Planck, Insitut Informatik
In the analysis of algorithms we are usually interested in obtaining closed form expressions for their complexity, or at least asymptotic expressions in O(Delta)-notation. Unfortunately, there are...