Moshe Lewenstein

The Subset Matching problem was recently introduced by Cole and Hariharan. The input of the problem is a text array of n sets totaling s elements and a pattern array of m sets totaling s0 elements....

Abstract. Two equal length strings, or two equal sized two dimensional texts, parameterize match (p-match) if there is a one-one mapping (relative to the alphabet) of their characters. Two...

Moshe Lewenstein, Maxim Sviridenko

1 Introduction Let S and S0 be two equal length strings. We say that S and S0 parameterizematch, or p-match for short, if there is a bijection ss from the alphabet of S to thealphabet of S0 such that...

\Lambda (2008)

Abstract The asymmetric maximum travelling salesman problem, also known as the Taxicab Ripoff problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with...

Efficient One Dimensional Real Scaled Matching (2008)

Two equal length strings, or two equal sized two dimensional texts, parameterize match (p-match) if there is a one-one mapping (relative to the alphabet) of their characters. Two dimensional...

Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur

Real Scaled Matching is the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Real scaled matching is an...

Abstract Dotted Interval Graphs and High Throughput Genotyping (2008)

Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter

We introduce a generalization of interval graphs, which we call dotted interval graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (=dotted intervals). Coloring...

Bar-Ilan University Bar-Ilan University Bar-Ilan University Bar-Ilan University (2008)

Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat

We present problems in three different application areas: identifying similar code where global register reallocation and spill code minimization were done (programming languages); protein threading...

Constructive bounds on ordered factorizations (2008)

Moshe Lewenstein, Moshe Lewenstein

LIMITED DISTRIBUTION NOTICE: This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. Ithas been issued as a Research Report for...

Two-Dimensional Range Minimum Queries ⋆ (2008)

Abstract Two equal length strings, or two equal sized two dimensional texts, parameterize match (p-match) if there is a one-one mapping (relative to the alphabet) of their characters. Two dimensional...

Amihood Amir, Johannes Fischer, Moshe Lewenstein

Abstract. We consider the two-dimensional Range Minimum Query problem: for a static (m × n)-matrix of size N = mn which may be preprocessed, answer on-line queries of the form “where is the...

z Bar-Ilan University Bar-Ilan University Bar-Ilan University (2007)

Alternation and Bounded Concurrency are Reverse Equivalent (2007)

Let a text string T of n symbols and a pattern string P of m symbols from alphabet \Sigma be given. A swapped version P 0 of P is a length m string derived from P by a series of local swaps, (i.e. p 0

Tirza Hirst, Moshe Lewenstein

Numerous models of concurrency have been considered in the framework of automata. Among the more interesting concurrency models are classical nondeterminism and pure concurrency, the two facets of...

x Georgia Tech Polytechnic University Bar-Ilan University Bar-Ilan University (2007)

Amihood Amir, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein

Let a text string T of n symbols and a pattern string P of m symbols from alphabet \Sigma be given. A swapped version T 0 of T is a length n string derived from T by a series of local swaps, (i.e. t 0

Optimization problems in multipleinterval graphs (2007)

Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. We initiate the study of optimization problems in...

Optimization problems in multipleinterval graphs (2007)

Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz

Abstract. Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. We initiate the study of optimization problems...

Range non-overlapping indexing and successive list indexing (2007)

Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein

Abstract. We present two natural variants of the indexing problem: In the range non-overlapping indexing problem, we preprocess a given text to answer queries in which we are given a pattern, and...

Dotted interval graphs and high throughput genotyping (2005)

Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Pinter, Zohar Yakhini

We introduce a generalization of interval graphs, which we call dotted interval graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (=dotted intervals). Coloring...

Approximate parameterized matching (2004)

Carmit Hazay, Moshe Lewenstein, Dina Sokol

Abstract Two equal length strings s and s0, over alphabets \Sigma s and \Sigma s0, parameterize match if thereexists a bijection ss: \Sigma s! \Sigma s0, such that ss(s) = s0, where ss(s) is the...

Approximate parameterized matching (2004)

Carmit Hazay, Moshe Lewenstein, Dina Sokol

Two equal length strings s and s ′ , over alphabets Σs and Σs ′, parameterize match if there exists a bijection π: Σs → Σs ′, such that π(s) = s ′ , where π(s) is the renaming of...

Approximate parameterized matching (2004)

Carmit Hazay, Moshe Lewenstein, Dina Sokol

Two equal length strings s and s ′ , over alphabets Σs and Σs ′, parameterize match if there exists a bijection π: Σs → Σs ′, such that π(s) = s ′ , where π(s) is the renaming of...

Overlap matching (2003)

Amir, Amihood, Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as...

Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs (2003)

Haim Kaplan, Nira Shafrir, Moshe Lewenstein, Maxim Sviridenko

A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall’s theorem one can represent such a multigraph as a combination of at most n 2 cycle...

A 5/8 approximation algorithm for the asymmetric maximum TSP (2002)

Moshe Lewenstein, Maxim Sviridenko

Abstract The Asymmetric Maximum Travelling Salesperson problem, also known as the Taxicab Ripoff problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with...

A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)

Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely

We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...

Overlap Matching (2001)

Amir, Amihood, Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...

A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)

Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely

We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...

Overlap Matching (2001)

Amir, Amihood, Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...

A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)

Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...

Overlap matching (2001)

Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...

A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)

Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...

Approximate subset matching with don’t cares (2001)

Faster algorithms for string matching with k mismatches (2000)

The need for the general task of "pattern matching" is ubiquitous. However, the combinatorial model of the problem varies with the different application domain.

Faster algorithms for string matching with k mismatches (2000)

The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length m and every length m substring of the text T. Currently, the fastest algorithms...

Faster Algorithms for String Matching with k Mismatches (2000)

The string matching with mismatches problem is that of finding the number of mismatches between pattern P of length m and every length m substring of the text T. Currently, the best algorithms for...