We present polynomial-time approximation algorithms for string folding problems over any finite alphabet. Our idea is the following: describe a class of feasible solutions by means of an ambiguous context-free grammar (i.e. there is a bijection between the set of parse trees and a subset of possible embeddings of the string); give a score to every production of the grammar, so that the total score of every parse tree (the sum of the scores of the productions of the tree) equals the score of the corresponding structure; apply a parsing algorithm to fi nd the parse tree with the highest score, corresponding to the con guration with highest score among those generated by the grammar. Furthermore, we show how the same approach can be extended in order to deal with an in finite alphabet or di erent goal functions. In each case, we prove that our algorithm guarantees a performance ratio that depends on the size of the alphabet or, in case of an in nite alphabet, on the length of the input string, both for the two and three-dimensional problem. Finally, we show some experimental results for the algorithm, comparing it to other performance-guaranteed approximation algorithms
Pavesi, G., Mauri, G. (2000). Approximation algorithms for string folding problems. In Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics. International Conference IFIP TCS 2000 Sendai, Japan, August 17–19, 2000 Proceedings (pp.45-58). Berlin : Springer-Verlag [10.1007/3-540-44929-9_4].
Approximation algorithms for string folding problems
MAURI, GIANCARLO
2000
Abstract
We present polynomial-time approximation algorithms for string folding problems over any finite alphabet. Our idea is the following: describe a class of feasible solutions by means of an ambiguous context-free grammar (i.e. there is a bijection between the set of parse trees and a subset of possible embeddings of the string); give a score to every production of the grammar, so that the total score of every parse tree (the sum of the scores of the productions of the tree) equals the score of the corresponding structure; apply a parsing algorithm to fi nd the parse tree with the highest score, corresponding to the con guration with highest score among those generated by the grammar. Furthermore, we show how the same approach can be extended in order to deal with an in finite alphabet or di erent goal functions. In each case, we prove that our algorithm guarantees a performance ratio that depends on the size of the alphabet or, in case of an in nite alphabet, on the length of the input string, both for the two and three-dimensional problem. Finally, we show some experimental results for the algorithm, comparing it to other performance-guaranteed approximation algorithmsI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.