Approximation Algorithms
- Richard Cole, Ramesh Hariharan, Moshe Lewenstein and Ely Porat.
A Faster Implementation
of the Goemans-Williamson Clustering Algorithm.
Proc. of SODA
2001, 17-25.
- Moshe Lewenstein and Maxim Sviridenko.
A 5/8 Approximation
Algorithm for the Maximum Asymmetric TSP.
SIAM J. on Discrete
Math, 17(2): 237-248, 2003.
(a preliminary version appeared in SODA 2003 under the
title "Approximating Maximum Asymmetric TSP".)
powerpoint
slides
- Haim Kaplan, Moshe Lewenstein, Nira Shafrir and Maxim Sviridenko.
Approximation
Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs.
J. of the ACM, 52(4): 602-626, 2005.
(a preliminary version
appeared in FOCS 2003 under the title "A
2/3 Approximation for Maximum Asymmetric TSP by Decomposing Directed Regular
Multigraphs".)
- David Gamarnik, Moshe Lewenstein and Maxim Sviridenko.
An Improved Upper Bound for TSP in Cubic
3-Connected Graphs.
Operations Research Letters, Vol. 33(5):
467-474, 2005.
- Zvi Gotthilf and Moshe Lewenstein.
Tighter Approximations for Maximum Induced
Matchings in Regular Graphs.
Proc. of WAOA 2005,
270-281.
High Dimensional Computational Geometry
- Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, Ely Porat.
Closest Pair Problems in Very High Dimensions.
Proc. of ICALP 2004, 782-792.
Formal Models
- Tirza Hirst and Moshe Lewenstein.
Alternation and Bounded
Concurrency are Reverse Equivalent.
Information and
Computation, 152(2), 173-187, 1999.
Combinatorics and Graph Theory
- Martin C. Golumbic and Moshe Lewenstein.
New Results on Strong
Matchings.
Discrete Applied Math, 101 (1-3),
157-165, 2000.
- Martin C. Golumbic, Tirza Hirst and Moshe Lewenstein.
Uniquely Restricted
Matchings.
Algorithmica, 31(2), 139-154, 2001.
- Don Coppersmith and Moshe Lewenstein.
Constructive Bounds on Ordered Factorizations.
SIAM J. on Discrete Math, 19(2): 301-303, 2005.
Pattern Matching
- Amihood Amir, Alberto Apostolico and Moshe Lewenstein.
Inverse Pattern
Matching.
Journal of Algorithms, 1997, Vol. 24,
325-339.
- Amihood Amir, Moshe Lewenstein and Noa Lewenstein.
Pattern Matching in
Hypertext.
Journal of Algorithms, 2000, 35(1),
82-99.
Also appeared in Proc. of WADS, 1997, 160-173.
- Amihood Amir, Yonatan Aumann, Gad Landau, Moshe Lewenstein and Noa
Lewenstein.
Pattern Matching with
Swaps.
Journal of Algorithms, 2000, Vol. 37(2),
247-266.
Also appeared in Proc. of FOCS, 1997, 148-153.
- Amihood Amir, Gad Landau, Moshe Lewenstein and Noa Lewenstein.
Efficient Special
Cases of Pattern Matching with Swaps.
Information
Processing Letters, 1998, Vol. 68(3), 125-132.
Also appeared in
Proc. of CPM, 1998, 209-220.
- Amihood Amir, Dmitry Keselman, Gad Landau, Moshe Lewenstein, Noa
Lewenstein and Michael Rodeh.
Indexing and
Dictionary Matching with One Error.
Journal of Algorithms,
2000, 37(2), 309-325.
Also appeared in Proc. of WADS, 1999,
181-192.
- Amihood Amir, Ayelet Butman and Moshe Lewenstein.
Real Scaled
Matching.
Information Processing Letters, 1999, Vol. 70(4),
185-190.
Also appeared in Proc. of SODA, 2000, 815-816.
- Amihood Amir, Moshe Lewenstein and Ely Porat.
Faster String
Matching with k Mismatches.
J. of Algorithms, 50(2):257-275 (special SODA issue).
(preliminary
version appeared in Proc. of SODA, 2000,
794-803.)
powerpoint slides of
survey on topic
- Amihood Amir, Moshe Lewenstein and Ely Porat.
Approximate Swapped
Matching.
Information Processing Letters, 83(1):33-39, 2002.
(preliminary
version appeared in Proc. of FSTTCS 2000, 302-331.)
- Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein and Ely
Porat.
Overlap
Matching.
Information and Computation, 181(1), 57-74,
2003.
(preliminary version appeared in Proc. of SODA 2001, 305-306.)
- Amihood Amir, Moshe Lewenstein and Ely Porat.
Approximate Subset
Matching with Don't Cares.
Proc. of SODA 2001,
279-288.
- Richard Cole and Moshe Lewenstein.
Multidimensional
Matching and Fast Search in Suffix Trees.
Proc. of SODA
2003, 851-852.
- Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein and Ely
Porat.
Function
Matching: Algorithms, Applications and a Lower Bound.
Proc. of
ICALP 2003, 929-942.
powerpoint
slides
- Amihood Amir, Ayelet Butman, Moshe Lewenstein and Ely Porat.
Real
Two Dimensional Scaled Matching.
Proc. of WADS 2003,
353-364.
powerpoint
slides
- Amihood Amir, Gan Landau, Moshe Lewenstein and Dina Sokol.
Dynamic Pattern,
Static Text Matching.
To appear in ACM Trans. on Algorithms.
(preliminary version appeared in Proc. of WADS 2003, 340-352.)
powerpoint
slides
- Richard Cole, Lee-Ad Gottlieb and Moshe Lewenstein.
Dictionary
matching and indexing with errors and don't cares.
Proc. of STOC
2004, 91-100.
- Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur.
Efficient One Dimensional Real Scaled Matching.
Proc. of SPIRE 2004, 1-9.
- Carmit Hazay, Moshe Lewenstein, Dina Sokol.
Approximate Parameterized Matching.
To appear in ACM Trans. on Algorithms.
(preliminary version appeared in Proc. of ESA 2004, 414-425)
- Carmit Hazay, Moshe Lewenstein, Dekel Tsur.
Two Dimensional Parameterized Matching.
Proc. of CPM 2005, 266-279.
- Amihood Amir, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein.
Towards Real Time Indexing.
Proc. of SPIRE 2005, 67-78.
- Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein.
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing.
To appear in Proc. of ICALP 2006.
- Nikhil Bansal, Moshe Lewenstein, Bin Ma, Kaizhong Zhang..
On the Longest Common Rigid Subsequence Problem.
Manuscript.
- Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur.
Finding Witnesses by Peeling.
Manuscript.
Computational Biology
- Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Pinter and Zohar
Yakhini.
Dotted Interval Graphs and High Throughput Genotyping.
Proc. of SODA
2005, 339-348.