Arrow Research search

Author name cluster

Rudolf Fleischer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers
2 author rows

Possible papers

15

TCS Journal 2014 Journal Article

Order-preserving matching

  • Jinil Kim
  • Peter Eades
  • Rudolf Fleischer
  • Seok-Hee Hong
  • Costas S. Iliopoulos
  • Kunsoo Park
  • Simon J. Puglisi
  • Takeshi Tokuyama

We introduce a new string matching problem called order-preserving matching on numeric strings, where a pattern matches a text if the text contains a substring of values whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching is closely related to the representation of order relations of a numeric string. We define the prefix representation and the nearest neighbor representation of the pattern, both of which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O ( n log m ) time algorithm and optimize it further to obtain O ( n + m log m ) time. For the multiple pattern case, we give an O ( n log m ) time algorithm.

Details DOI

TCS Journal 2012 Journal Article

An algorithmic analysis of the Honey-Bee game

  • Rudolf Fleischer
  • Gerhard J. Woeginger

The Honey-Bee game is a two-player board game that is played on a connected hexagonal colored grid or (in a generalized setting) on a connected graph with colored nodes. In a single move, a player calls a color and thereby conquers all the nodes of that color that are adjacent to his own current territory. Both players want to conquer the majority of the nodes. We show that winning the game is PSPACE-hard in general, NP-hard on series-parallel graphs, but easy on outer-planar graphs. In the solitaire version, the goal of the single player is to conquer the entire graph with the minimum number of moves. The solitaire version is NP-hard on trees and split graphs, but can be solved in polynomial time on co-comparability graphs.

Details DOI

TCS Journal 2006 Journal Article

Approximating the minimum weight weak vertex cover

  • Yong Zhang
  • Qi Ge
  • Rudolf Fleischer
  • Tao Jiang
  • Hong Zhu

Accurate network flow measurement is important for a variety of network applications, where the “flow” over an edge in the network is intuitively the rate of data traffic. The problem of efficiently monitoring the network flow can be regarded as finding the minimum weight weak vertex cover for a given graph. In this paper, we present a ( 2 - 2 ν ( G ) ) -approximation algorithm solving for this problem, which improves previous results, where ν ( G ) is the cyclomatic number of G.

Details DOI

TCS Journal 2004 Journal Article

New results for online page replication

  • Rudolf Fleischer
  • Włodzimierz Głazek
  • 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 randomized online algorithm is better than 1. 75037-competitive on the ring; previously, only a 1. 58198 bound for a single edge was known. We extend the problem in several new directions: continuous metrics, variable size requests, and replication before service. This yields simplified proofs of several known results.

Details DOI

TCS Journal 2004 Journal Article

Solitaire Clobber

  • 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 and black moves. We show that a n stone checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones. For boards with at least two rows and two columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones. We also show that in general it is NP-complete to decide whether an arbitrary Clobber configuration can be reduced to a single stone.

Details DOI

TCS Journal 2004 Journal Article

Traveling salesmen in the presence of competition

  • Sándor P. Fekete
  • Rudolf Fleischer
  • Aviezri Fraenkel
  • Matthias Schmitt

We propose the “competing salesmen problem” (CSP), a two-player competitive version of the classical traveling salesman problem. This problem arises when considering two competing salesmen instead of just one. The concern for a shortest tour is replaced by the necessity to reach any of the customers before the opponent does. In particular, we consider the situation where players take turns, moving along one edge at a time within a graph G=(V, E). The set of customers is given by a subset V C⊆V of the vertices. At any given time, both players know of their opponent's position. A player wins if he is able to reach a majority of the vertices in V C before the opponent does. We prove that the CSP is PSPACE-complete, even if the graph is bipartite, and both players start at distance 2 from each other. Furthermore, we show that the starting player may not be able to avoid losing the game, even if both players start from the same vertex. However, for the case of bipartite graphs, we show that the starting player always can avoid a loss. On the other hand, we show that the second player can avoid to lose by more than one customer, when play takes place on a graph that is a tree T, and V C consists of leaves of T. It is unclear whether a polynomial strategy exists for any of the two players to force this outcome. For the case where T is a star (i. e. , a tree with only one vertex of degree higher than two) and V C consists of n leaves of T, we give a simple and fast strategy which is optimal for both players. If V C consists not only of leaves, we point out that the situation is more involved.

Details DOI

TCS Journal 2001 Journal Article

On the Bahncard problem

  • Rudolf Fleischer

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 Bundesbahn (the German railway company) which entitles its holder to a 50% price reduction on nearly all train tickets. It costs 240 DM, and it is valid for 12 months. Similar bus or railway passes can be found in many other countries. For the common traveler, the decision at which time to buy a Bahncard is a typical online problem, because she usually does not know when and where she will travel next. We show that the greedy algorithm applied by most travelers and clerks at ticket offices is not better in the worst case than the trivial algorithm which never buys a Bahncard. We present two optimal deterministic online algorithms, an optimistic one and a pessimistic one. We further give a lower bound for randomized online algorithms and present an algorithm which we conjecture to be optimal; a proof of the conjecture is given for a special case of the problem. It turns out that the optimal competitive ratio only depends on the price reduction factor (50% for the German Bahncard Problem), but does not depend on the price or validity period of a Bahncard.

Details DOI

I&C Journal 2001 Journal Article

Optimal Robot Localization in Trees

  • Rudolf Fleischer
  • Kathleen Romanik
  • Sven Schuierer
  • Gerhard Trippen

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 aerial photography to autonomous vehicle exploration. In 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 exploits to a high degree the self-similarities that may occur in the environment. We use the framework of competitive analysis to analyze the performance of our strategy. In particular, we show that the distance traveled by the robot is at most O( n ) times longer than the shortest possible route to localize the robot, where n is the number of vertices of the tree. This is a significant improvement over the best known previous bound of O(n 2/3). Moreover, since there is a lower bound of Ω( n ), our strategy is optimal up to a constant factor. Using the same approach we can also show that the problem of searching for a target in a geometric tree, where the robot is given a map of the tree and the location of the target but does not know its own position, can be solved by a strategy with a competitive ratio of O( n ), which is again optimal up to a constant factor.

Details DOI

MFCS Conference 2000 Conference Paper

Balanced k -Colorings

  • Therese C. Biedl
  • Eowyn Cenek
  • Timothy M. Chan
  • Erik D. Demaine
  • Martin L. Demaine
  • Rudolf Fleischer
  • Ming-wei Wang

Abstract 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 vertices. The imbalance is the maximum, over all subsets in the family, of the largest difference between the size of any two color classes in that subset. The discrepancy is the minimum possible imbalance. We show that the discrepancy is always at most 4d - 3, where d (the “dimension”) is the maximum number of subsets containing a common vertex. For 2-colorings, the bound on the discrepancy is at most max{2d-3, 2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete.

Details

I&C Journal 1999 Journal Article

Decision Trees: Old and New Results

  • Rudolf Fleischer

In this paper, we prove two general lower bounds for algebraic decision trees which test membership in a set S⊆ R n which is defined by linear inequalities. Let rank(S) be the maximal dimension of a linear sub- space contained in the closure of S (in Euclidean topology). First we show that any decision tree for S which uses products of linear functions (we call such functions mlf-functions) must have depth at least n−rank(S). This solves an open question raised by A. C. Yao and can be used to show that mlf-functions are not really more powerful than simple comparisons between the input variables when computing the largest k out of n elements. Yao proved this result in the special case when products of at most two linear functions are allowed. Our proof also shows that any decision tree for this problem must have exponential size. Using the same methods, we can give an alternative proof of Rabin's theorem, namely that the depth of any decision tree for S using arbitrary analytic functions is at least n−rank(S).

Details DOI
v2026.09.13