Ron Shamir

I&C Journal 2006 Journal Article

A simpler and faster 1.5-approximation algorithm for sorting by transpositions

• Tzvika Hartman
• Ron Shamir

An important problem in genome rearrangements is sorting permutations by transpositions. The complexity of the problem is still open, and two rather complicated 1. 5-approximation algorithms for sorting linear permutations are known (Bafna and Pevzner, 98 and Christie, 99). The fastest known algorithm is the quadratic algorithm of Bafna and Pevzner. In this paper, we observe that the problem of sorting circular permutations by transpositions is equivalent to the problem of sorting linear permutations by transpositions. Hence, all algorithms for sorting linear permutations by transpositions can be used to sort circular permutations. Our main result is a new O ( n 3 / 2 log n ) 1. 5-approximation algorithm, which is considerably simpler than the previous ones, and whose analysis is significantly less involved.

STOC Conference 1998 Conference Paper

A Polynomial Approximation Algorithm for the Minimum Fill-In Problem

• Assaf Natanzon
• Ron Shamir
• Roded Sharan

SODA Conference 1998 Conference Paper

The Maximum Subforest Problem: Approximation and Exact Algorithms (Extended Abstract)

• Ron Shamir
• Dekel Tsur

SODA Conference 1997 Conference Paper

Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals

• Haim Kaplan
• Ron Shamir
• Robert Endre Tarjan

TCS Journal 1997 Journal Article

Satisfiability problems on intervals and unit intervals

• Itsik Pe'er
• Ron Shamir

For an interval graph with some additional order constraints between pairs of non-intersecting intervals, we give a linear time algorithm to determine if there exists a realization which respects the order constraints. Previous algorithms for this problem (known also as seriation with side constraints) required quadratic time. This problem contains as subproblems interval graph and interval order recognition. On the other hand, it is a special case of the interval satisfiability problem, which is concerned with the realizability of a set of intervals along a line, subject to precedence and intersection constraints. We study such problems for all possible restrictions on the types of constraints, when all intervals must have the same length. We give efficient algorithms for several restrictions of the problem, and show the NP-completeness of another restriction.

FOCS Conference 1994 Conference Paper

Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping

• Haim Kaplan
• Ron Shamir
• Robert Endre Tarjan

We study the parameterized complexity of several NP-Hard graph completion problems: The minimum fill-in problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k/sup 5/ mn+f(K)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). proper interval graph completion problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)n/sup k-1/) algorithm, so it is polynomial for fixed k. On the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect. >

SODA Conference 1990 Conference Paper

Characterization and Algorithms for Greedily Solvable Transportation Problems

• Ron Shamir
• Brenda L. Dietrich