Efficient Algorithms for k-Disjoint Paths Problems on DAGs ⋆ (2009)
Rudolf Fleischer, Qi Ge, Jian Li, Hong Zhu
Abstract. Given an acyclic directed graph and two distinct nodes s and t, we consider the problem of finding k disjoint paths from s to t satisfying some objective. We consider four objectives,...
Approximating Spanning Tree with Weighted Inner Nodes (2008)
Jian Li, Haitao Wang, Rudolf Fleischer, Qi Ge, Hong Zhu
Abstract. We consider a problem coming from practical applications: finding a minimum spanning tree with both edge weights and inner node (non-leaf node) weights. This problem is NP-complete even in...
Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory (2008)
Erik D. Demaine, Rudolf Fleischer, Aviezri S. Fraenkel, Richard J. Nowakowski
This is list of combinatorial games problems collected at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, organized by the authors. For more unsolved problems in combinatorial...
Just-in-Time: Better Teaching in Hong Kong (2008)
I report on my experiences with Just-in-Time Teaching (JiTT) in the course COMP272 (Theory of Computing) at the Hong Kong University of Science and Technology. The course was given in Spring 2002 and...
Approximating Spanning Trees with Inner Nodes Cost (2008)
Rudolf Fleischer, Qi Ge, Jian Li, Shijun Tian, Haitao Wang
We consider the practical NP-complete problem of finding a minimum weight spanning tree with both edge weights and inner nodes weights. We present two polynomial time algorithms with approximation...
Rudolf Fleischer, Mordecai J. Golin, Zhang Yan
Abstract. The standard dynamic programming solution to finding kmedians on a line with n nodes requires O(kn 2) time. Dynamic programming speed-up techniques, e.g., use of the quadrangle inequality...
Rudolf Fleischer, Hisashi Koga
In current networks, packet losses can occur if routers do not provide sufficiently large buffers. This paper studies how many buffers should be provided in a router to eliminate packet losses. We...
Traversing the Machining Graph (2008)
Danny Z. Chen, Rudolf Fleischer, Haitao Wang, Hong Zhu
Abstract. Zigzag pocket machining (or 2D-milling) plays an important role in the manufacturing industry. The objective is to minimize the number of tool retractions in the zigzag machining path for a...
Approximating the Maximum Sharing Problem (2008)
Amitabh Chaudhary, Danny Z. Chen, Rudolf Fleischer, Xiaobo S. Hu, Jian Li, Michael T. Niemier, ...
In the maximum sharing problem (MS), we want to compute a set of (non-simple) paths in an undirected bipartite graph covering as many nodes as possible of the first layer of the graph, with the...
Traversing the Machining Graph (2008)
Danny Z. Chen, Rudolf Fleischer, Jian Li, Haitao Wang, Hong Zhu
Abstract. Zigzag pocket machining (or 2D-milling) plays an important role in the manufacturing industry. The objective is to minimize the number of tool retractions in the zigzag machining path for a...
Non-Metric Multicommodity and Multilevel Facility Location (2008)
Rudolf Fleischer, Jian Li, Shijun Tian, Hong Zhu
Abstract. We give logarithmic approximation algorithms for the nonmetric uncapacitated multicommodity and multilevel facility location problems. The former algorithms are optimal up to a constant...
Federal Republic of Germany (2008)
Helmut Alt, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn, Stefan Schirra, Christian Uhrig, ...
Abstract: We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time f~(n 2) where n is the number of obstacle corners. We...
Algorithms for Core Stability, Core Largeness, Exactness, and Extendability of Flow Games ⋆ (2008)
Qizhi Fang, Rudolf Fleischer, Xiaoxun Sun
Abstract. In this paper, we give linear time algorithms to decide core stability, core largeness, exactness, and extendability of flow games on uniform networks (all edge capacities are 1). We show...
On the Effectiveness of Visualizations in a Theory of Computing Course (2008)
Abstract. We report on two tests we performed in Hong Kong and Shanghai to verify the hypothesis that one can learn better when being given access to visualizations beyond the standard verbal...
Communicated by Editor’s name In this paper we show how a slight modification of (a, 2b)-trees allows us to perform member and neighbor queries in O(log n) time and updates in O(1) worst-case time...
Algorithms for Core Stability, Core Largeness, Exactness, and Extendability of Flow Games ⋆ (2008)
Qizhi Fang, Rudolf Fleischer, Jian Li, Xiaoxun Sun
Abstract. In this paper, we give linear time algorithms to decide core stability, core largeness, exactness, and extendability of flow games on uniform networks (all edge capacities are 1). We show...
Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory (2008)
Erik D. Demaine, Rudolf Fleischer, Aviezri S. Fraenkel, Richard J. Nowakowski
This is list of combinatorial games problems collected at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, organized by the authors. For more unsolved problems in combinatorial...
Competitive Online Searching for a Ray in the Plane ⋆ Abstract (2008)
Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The search agent finds the flashlight as soon as it crosses the ray emanating from the...
Competitive Online Searching for a Ray in the Plane (2008)
Andrea Eubeler Rudolf, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
We consider the problem of a searcher that looks for a lost flashlight in a dusty environment. The search agent finds the flashlight as soon as it crosses the ray emanating from the flashlight, and...
Algorithm Animation for Teaching (2008)
Rudolf Fleischer, Ludek Kucera
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...
Page Replication--- Variations on a Theme (2007)
Rudolf Fleischer, Steve Seiden
Abstract. 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...
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...
Therese C. Biedl, Eowyn 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...
Ab Imbi Begr, Ab Imbi, Begr Uung, Peter Damaschke (hagen, Uwe Schwiegelshohn (dortmund, John J. Turek, ...
: 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...
FUN with Implementing Algorithms (2007)
. 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...
A Simple Balanced Search Tree With O(1) Worst-Case Update Time (2007)
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...
Kayles on the Way to the Stars (2007)
Abstract. We present several new results on the impartial two-person game Kayles. The original version is played on a row of pins (\kayles"). We investigate variants of the game played on...
Rudolf Fleischer, Mordecai J. Golin, Zhang Yan
Abstract. The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(kn 2) time. Dynamic programming speed-up techniques, e.g., use of the quadrangle inequality...
14 Second Program Visualization Workshop The Algorithm Animation Repository (2007)
Pierluigi Crescenzi, Nils Faltin, Rudolf Fleischer, Christopher Hundhausen, Stefan Näher, Guido Rößling, ...
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 are normally...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Abstract. 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...
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...
Xiangqi and Combinatorial Game Theory (2007)
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...
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...
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...
On The Bahncard Problem (2007)
Abstract. 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...
Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang
b;1
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...
Rudolf Fleischer, Wlodzimierz Glazek, Steve Seiden
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...
Finding Optimal Paths in MREP Routing (2007)
Rudolf Fleischer Mordecai, 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...
Fun-Sort --- Or the Chaos of Unordered (2007)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
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...
Open Problems At, 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...
Abstract. The Hydra was a many-headed monster from Greek mythology that would immediately replace a head that was cut off by one or two new heads. It was the second task of Hercules to kill this...
Abstract. The hydra was a many-headed monster from Greek mythology that could grow one or two new heads when one of its heads got cut off. It was the second task of Hercules to kill this monster. In...
Competitive Online Searching for a Ray in the Plane (2007)
Eubeler, Andrea, Fleischer, Rudolf, Kamphans, Tom, Klein, Rolf, Langetepe, Elmar, Trippen, Gerhard
We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The searcher finds the flashlight as soon as it crosses the ray emanating from the...
06421 Executive Summary -- Robot Navigation (2007)
Fekete, Sándor, Fleischer, Rudolf, Klein, Rolf, Lopez-Ortiz, Alejandro
For quite a number of years, researchers from various fields have studied problems motivated by Robot Navigation. People in Online Algorithms have developed strategies that can deal with the inherent...
06421 Abstracts Collection -- Robot Navigation (2007)
Fekete, Sándor, Fleischer, Rudolf, Klein, Rolf, Lopez-Ortiz, Alejandro
From 15.10.06 to 20.10.06, the Dagstuhl Seminar 06421 ``Robot Navigation''generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the...
On approximating the maximum simple sharing problem (2006)
Danny Z. Chen, Rudolf Fleischer, Jian Li, Zhiyi Xie, Hong Zhu
Abstract. In the maximum simple sharing problem (MSS), we want to compute a set of node-disjoint simple paths in an undirected bipartite graph covering as many nodes as possible of one layer of the...
On approximating the maximum simple sharing problem (2006)
Danny Z. Chen, Rudolf Fleischer, Zhiyi Xie, Hong Zhu
Abstract. In the maximum simple sharing problem (MSS), wewantto compute a set of node-disjoint simple paths in an undirected bipartite graph covering as many nodes as possible of one layer of the...
The hydra was a many-headed monster from Greek mythology that could grow one or two new heads when one of its heads got cut off. It was the second task of Hercules to kill this monster. In an...
Competitive online searching for a ray in the plane (2005)
Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe
We consider the problem of a searcher that looks for a lost flashlight in a dusty environment. The search agent finds the flashlight as soon as it crosses the ray emanating from the flashlight, and...
Exploring an unknown graph efficiently (2005)
Abstract. We study the problem of exploring an unknown, strongly connected directed graph. Starting at some node of the graph, we must visit every edge and every node at least once. The goal is to...
Pareto-optimality in house allocation problems (2005)
Abraham, David, Mehlhorn, Kurt, Fleischer, Rudolf, Trippen, G.
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, 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...
Online Maintenance of KMedians and K-Covers on a Line (2004)
Rudolf Fleischer, Mordecai J. Golin, Yan Zhang
The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(kn 2) time. Dynamic programming speedup techniques, e.g., use of the quadrangle inequality or...
Tight bounds on maximal and maximum matchings (2004)
Therese Biedl, Erikd. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
Abstract. 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...
Online Maintenance of KMedians and K-Covers on a Line (2004)
Rudolf Fleischer, Mordecai J. Golin, Yan Zhang
The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(kn 2) time. Dynamic programming speedup techniques, e.g., use of the quadrangle inequality or...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Abstract. 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...
Tight bounds on maximal and maximum matchings (2004)
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
Abstract. 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...
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...
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...
Traveling Salesmen in the Presence of Competition (2004)
Sándor 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...
Balances Scheduling toward Loss-Free Packet Queuing and Delay Fairness (2004)
Rudolf Fleischer, Hisashi Koga
In current networks, packet losses can occur if routers do not provide sufficiently large buffers. This paper studies how many buffers should be provided in a router to eliminate packet losses. We...
Competitive Online Approximation of the Optimal Search Ratio (2004)
Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen
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...
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Fleischer, Rudolf, ...
Polynomial deterministic rendezvous in arbitrary graphs (2004)
Kowalski, Dariusz, Pelc, Andrzej, Fleischer, Rudolf, Trippen, Gerhard
Maximum residual energy routing with reverse energy cost (2003)
Qiling Xie, Chin-tau Lea, Mordecai J. Golin, Rudolf Fleischer
Abstract-The Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in a battery wireless network. Past studies on MREP are based on the...
Exploring the role of visualization and engagement in computer science education (2003)
Thomas L. Naps, Rudolf Fleischer, Myles Mcnally, Guido Rößling, Chris Hundhausen, Susan Rodger, ...
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...
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...
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...
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...
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...
The complexity of Clickomania (2002)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
Abstract. 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...
The complexity of Clickomania (2002)
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...
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...
The Complexity of Clickomania (2001)
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...
Optimal robot localization in trees (2000)
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...
Asymptotic complexity from experiments? A case study for randomized algorithms (2000)
Peter Sanders, Rudolf Fleischer, Max Planck, Insitut Informatik
Abstract. 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,...
New Results for Online Page Replication (2000)
Rudolf Fleischer, Wlodzimierz Glazek, 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...
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...
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...
Online Routing in Convex Subdivisions (2000)
Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, ...
. 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...
Asymptotic Complexity from Experiments? - A Case Study for Randomized Algorithms (2000)
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...
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)
Prosenjit Bose Andrej, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, ...
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...
A strong and easily computable separation bound for arithmetic expressions involving radicals (2000)
Burnikel, Christoph, Fleischer, Rudolf, Mehlhorn, Kurt, Schirra, Stefan
We consider arithmetic expressions over operators + , - , * , / , and $\sqrt[k]$ , with integer operands. For an expression E having value $\xi$ , a separation bound sep (E) is a positive real number...
Efficient exact geometric computation made easy (1999)
Burnikel, Christoph, Fleischer, Rudolf, Mehlhorn, Kurt, Schirra, Stefan
We show that the combination of the CGAL framework for geometric computation and the number type leda-real yields easy-to-write, correct and efficient geometric programs.
On the Bahncard Problem (1998)
. 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, 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...
ARTICLE NO. AL960824 More Efficient Parallel Totally Monotone Matrix Searching* (1996)
Phillip G. Bradford, Rudolf Fleischer, Michiel Smid
We give a parallel algorithm for computing all row minima in a totally monotone n � n matrix which is simpler and more work efficient than previous polylog-time algorithms. It runs in OŽ lg n lg...
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,...
A communication-randomness tradeoff for two-processor systems (1995)
Fleischer, Rudolf, Jung, Hermann, Mehlhorn, Kurt
We present a tight tradeoff between the expected communication complexity $\bar{C}$ (for a two-processor system) and the number $R$ of random bits used by any Las Vegas protocol for the...
Fun-Sort --- Or the Chaos of Unordered (1994)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
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...
Alt, Helmut, Fleischer, Rudolf, Kaufmann, Michael, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, ...
Simultaneous Inner and Outer Approximation of Shapes (1992)
Fleischer, Rudolf, Mehlhorn, Kurt, Rote, Günter, Welzl, Emo, Yap, Chee-Keng
Selected Topics from Computational Geometry, Data Structures and Motion Planning (1992)
Fleischer, Rudolf, Fries, Otfried, Mehlhorn, Kurt, Meiser, Stefan, Näher, Stefan, Rohnert, Hans, ...
A Time-Randomness Tradeoff for Communication Complexity (1991)
Fleischer, Rudolf, Jung, Hermann, Mehlhorn, Kurt, Van Leeuwen, Jan, Santoro, Nicola