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 algorithms
slide + paper
approximation algorithms, string folding
English
International Conference IFIP TCS 2000 Sendai, Japan, August 17–19, 2000
2000
Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics. International Conference IFIP TCS 2000 Sendai, Japan, August 17–19, 2000 Proceedings
9783540678236
2000
1872
45
58
none
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/16528
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
Social impact