The “mean speedup” of a trace monoid can be interpreted as an index of the “intrinsic parallelism”. We study the problem of computing the mean speedup under two conditions: (1) uniform distribution on the words of given length and (2) uniform distribution on the traces of given height. In the first case, we give an approximability result showing a probabilistic fully polynomial time approximation scheme, while, in the second case, we prove that the problem is NP-hard to approximate within n 1 − ε for every ε> 0, unless NP = coR.
Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids / A. Bertoni, R. Radicioni (LECTURE NOTES IN COMPUTER SCIENCE). - In: Developments in Language Theory / [a cura di] T. Harju, J. Karhumäki, A. Lepistö. - Berlin : Springer, 2007. - ISBN 9783540732075. - pp. 72-83 (( Intervento presentato al 11. convegno International Conference on Developments in Language Theory tenutosi a Turku, Finland nel 2007 [10.1007/978-3-540-73208-2_10].
Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids
A. BertoniPrimo
;R. RadicioniUltimo
2007
Abstract
The “mean speedup” of a trace monoid can be interpreted as an index of the “intrinsic parallelism”. We study the problem of computing the mean speedup under two conditions: (1) uniform distribution on the words of given length and (2) uniform distribution on the traces of given height. In the first case, we give an approximability result showing a probabilistic fully polynomial time approximation scheme, while, in the second case, we prove that the problem is NP-hard to approximate within n 1 − ε for every ε> 0, unless NP = coR.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
