The Maximum Equality-Free String Factorization Problem: Gaps vs. No Gaps

Radu Stefan Mincu, Alexandru Popa

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

Abstract

A factorization of a string w is a partition of w into substrings such that. Such a partition is called equality-free if no two factors are equal: with. The maximum equality-free factorization problem is to decide, for a given string w and integer k, whether w admits an equality-free factorization with k factors. Equality-free factorizations have lately received attention because of their application in DNA self-assembly. Condon et al. (CPM 2012) study a version of the problem and show that it is-complete to decide if there exists an equality-free factorization with an upper bound on the length of the factors. At STACS 2015, Fernau et al. show that the maximum equality-free factorization problem with a lower bound on the number of factors is-complete. Shortly after, Schmid (CiE 2015) presents results concerning the Fixed Parameter Tractability of the problems. In this paper we approach equality free factorizations from a practical point of view i.e. we wish to obtain good solutions on given instances. To this end, we provide approximation algorithms, heuristics, Integer Programming models, an improved FPT algorithm and we also conduct experiments to analyze the performance of our proposed algorithms. Additionally, we study a relaxed version of the problem where gaps are allowed between factors and we design a constant factor approximation algorithm for this case. Surprisingly, after extensive experiments we conjecture that the relaxed problem has the same optimum as the original.

Original languageEnglish
Title of host publicationSOFSEM 2020
Subtitle of host publicationTheory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings
EditorsAlexander Chatzigeorgiou, Riccardo Dondi, Herodotos Herodotou, Christos Kapoutsis, Yannis Manolopoulos, George A. Papadopoulos, Florian Sikora
PublisherSpringer
Pages531-543
Number of pages13
ISBN (Print)9783030389185
DOIs
Publication statusPublished - Jan 1 2020
Event46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020 - Limassol, Cyprus
Duration: Jan 20 2020Jan 24 2020

Publication series

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

Conference

Conference46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020
CountryCyprus
CityLimassol
Period1/20/201/24/20

    Fingerprint

Keywords

  • Equality-free
  • Heuristics
  • String algorithms
  • String factorization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Mincu, R. S., & Popa, A. (2020). The Maximum Equality-Free String Factorization Problem: Gaps vs. No Gaps. In A. Chatzigeorgiou, R. Dondi, H. Herodotou, C. Kapoutsis, Y. Manolopoulos, G. A. Papadopoulos, & F. Sikora (Eds.), SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings (pp. 531-543). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12011 LNCS). Springer. https://doi.org/10.1007/978-3-030-38919-2_43