Algorithms for closest and farthest string problems via rank distance

Liviu P. Dinu, Bogdan C. Dumitru, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings
EditorsT. V. Gopal, Junzo Watada
PublisherSpringer Verlag
Pages154-171
Number of pages18
ISBN (Print)9783030148119
DOIs
Publication statusPublished - Jan 1 2019
Event15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan
Duration: Apr 13 2019Apr 16 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11436 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019
CountryJapan
CityKitakyushu
Period4/13/194/16/19

Fingerprint

Strings
Polynomials
Linear programming
Computational complexity
Polynomial-time Algorithm
Integer
Integer Linear Programming
Exact Algorithms
Polynomial time
Continue
NP-complete problem
Likely
Heuristics
Formulation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Dinu, L. P., Dumitru, B. C., & Popa, A. (2019). Algorithms for closest and farthest string problems via rank distance. In T. V. Gopal, & J. Watada (Eds.), 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

Algorithms for closest and farthest string problems via rank distance. / Dinu, Liviu P.; Dumitru, Bogdan C.; Popa, Alexandru.

Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. ed. / T. V. Gopal; Junzo Watada. Springer Verlag, 2019. p. 154-171 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Dinu, LP, Dumitru, BC & Popa, A 2019, Algorithms for closest and farthest string problems via rank distance. in TV Gopal & J Watada (eds), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11436 LNCS, Springer Verlag, pp. 154-171, 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019, Kitakyushu, Japan, 4/13/19. https://doi.org/10.1007/978-3-030-14812-6_10
Dinu LP, Dumitru BC, Popa A. Algorithms for closest and farthest string problems via rank distance. In Gopal TV, Watada J, editors, Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Springer Verlag. 2019. p. 154-171. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-14812-6_10
Dinu, Liviu P. ; Dumitru, Bogdan C. ; Popa, Alexandru. / Algorithms for closest and farthest string problems via rank distance. Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. editor / T. V. Gopal ; Junzo Watada. Springer Verlag, 2019. pp. 154-171 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{5a7664cc436e4e8e800c3fdd74c7be0c,
title = "Algorithms for closest and farthest string problems via rank distance",
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.",
author = "Dinu, {Liviu P.} and Dumitru, {Bogdan C.} and Alexandru Popa",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-030-14812-6_10",
language = "English",
isbn = "9783030148119",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "154--171",
editor = "Gopal, {T. V.} and Junzo Watada",
booktitle = "Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings",
address = "Germany",

}

TY - GEN

T1 - Algorithms for closest and farthest string problems via rank distance

AU - Dinu, Liviu P.

AU - Dumitru, Bogdan C.

AU - Popa, Alexandru

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85064857144&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064857144&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14812-6_10

DO - 10.1007/978-3-030-14812-6_10

M3 - Conference contribution

AN - SCOPUS:85064857144

SN - 9783030148119

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

SP - 154

EP - 171

BT - Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings

A2 - Gopal, T. V.

A2 - Watada, Junzo

PB - Springer Verlag

ER -