### Abstract

A new distance between strings, termed rank distance, was introduced by Dinu (Fundamenta Informaticae, 2003). Since then, the properties of rank distance were studied in several papers. In this article, we continue the study of rank distance. More precisely we tackle three problems that concern the distance between strings. 1.The first problem that we study is String with Fixed Rank Distance (SFRD): given a set of strings S and an integer d decide if there exists a string that is at distance d from every string in S. For this problem we provide a polynomial time exact algorithm.2.The second problem that we study is named is the Closest String Problem under Rank Distance (CSRD). The input consists of a set of strings S, asks to find the minimum integer d and a string that is at distance at most d from all strings in S. Since this problem is NP-hard (Dinu and Popa, CPM 2012) it is likely that no polynomial time algorithm exists. Thus, we propose three different approaches: a heuristic approach and two integer linear programming formulations, one of them using geometric interpretation of the problem.3.Finally, we approach the Farthest String Problem via Rank Distance (FSRD) that asks to find two strings with the same frequency of characters (i.e. the same Parikh vector) that have the largest possible rank distance. We provide a polynomial time exact algorithm for this problem.

Original language | English |
---|---|

Title of host publication | Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings |

Editors | T. V. Gopal, Junzo Watada |

Publisher | Springer Verlag |

Pages | 154-171 |

Number of pages | 18 |

ISBN (Print) | 9783030148119 |

DOIs | |

Publication status | Published - Jan 1 2019 |

Event | 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan Duration: Apr 13 2019 → Apr 16 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11436 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 |
---|---|

Country | Japan |

City | Kitakyushu |

Period | 4/13/19 → 4/16/19 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings*(pp. 154-171). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-14812-6_10