Towards Ambitious Approximation Algorithms in Stubborn Set Optimization

• Autorzy: Varpaaniemi K.
• Języki publikacji: EN

Abstrakty

EN

This article continues research on the stubborn set method that constructs on-the-fly a reduced LTS that is CFFD-equivalent to the parallel composition of given LTSs. In particular, minimization of the number of successor states of a given state is reconsidered. The earlier suggested and/or-graph approach requires solving #P-complete counting problems in order to get the weights for the vertices of the and/or-graph. The ``branch-and-bound'' decision problem corresponding to the minimization of the sum of the computed weights is ``only'' NP-complete. Unfortunately, #P-complete counting does not seem easily avoidable in the general case because it is PP-complete to check whether a given stubborn set produces at most as many successor states as another given stubborn set. Instead of solving each of the subproblems, one could think of computing approximate solutions in such a way that the total effect of the approximations is a useful approximation itself.

Słowa kluczowe

EN

Labelled Transition Systems (LTS); stubborn sets; and/or-graphs; approximability in optimization and counting

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 54, nr 2,3
• Strony: 279--294
• Opis fizyczny: bibliogr. 17 poz.

Twórcy

autor

Varpaaniemi K.

• Laboratory for Theoretical Computer Science, Helsinki University of Technology P.O. Box9205, FIN-02015 HUT, Finland,

Bibliografia

• [1] Angluin, D.: On Counting Problems and the Polynomial-Time Hierarchy, Theoretical Computer Science, 12(2), 1980, 161173.
• [2] Cerny, V.: Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm, Journal of Optimization Theory and Applications, 45(1), 1985, 41-51.
• [3] Crescenzi, P.: A Short Guide to Approximation Preserving Reductions, in: Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 1997, IEEE Computer Society, Los Alamitos CA, USA, 1997, 262-273.
• [4] Gill, J.: Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing, 6(4), 1977, 675-695.
• [5] Glover, F.: Tabu Search—Part I, ORSA Journal on Computing, 1(3), 1989, 190-206.
• [6] Karp, R. M., Luby, M., Madras, N.: Monte-Carlo Approximation Algorithms for Enumeration Problems, Journal of Algorithms, 10(3), 1989, 429-448.
• [7] Khanna, S., Sudan, M., Trevisan, L.: Constraint Satisfaction: The Approximability of Minimization Problems, in: Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 1997, IEEE Computer Society, Los Alamitos CA, USA, 1997, 282-296.
• [8] Kirkpatrick, S., Gelatt , C. D., Jr., Vecchi, M. P.: Optimization by Simulated Annealing, Science, 220(4598), 1983, 671-680.
• [9] Motwani, R., Raghavan, P.: Randomized Algorithms, Cambridge University Press, Cambridge, UK, 1995.
• [10] Sahni, S.: Computationally Related Problems, SIAM Journal on Computing, 3(4), 1974, 262-279.
• [11] Simon, J.: On Some Central Problems in Computational Complexity, PhD Thesis, Cornell University, Department of Computer Science, Technical Report TR 75-224, Ithaca NY, USA, January 1975.
• [12] Valiant, L. G.: The Complexity of Computing the Permanent, Theoretical Computer Science, 8(2), 1979, 189-201.
• [13] Valiant, L. G.: The Complexity of Enumeration and Reliability Problems, SIAM Journal on Computing, 8(3), 1979, 410-421.
• [14] Valmari, A.: Stubborn Set Methods for Process Algebras, in: Partial Order Methods in Verification (D. A. Peled, V. R. Pratt, G. J. Holzmann, Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 29, American Mathematical Society, Providence RI, USA, 1997, 213-231.
• [15] Valmari, A., Tienari, M.: Compositional Failure-Based Semantic Models for Basic LOTOS, Formal Aspects of Computing, 7(4), 1995, 440-468.
• [16] Varpaaniemi, K.: Stable Models for Stubborn Sets, Fundamenta Informaticae, 43(1-4), 2000, 355-375.
• [17] Varpaaniemi, K.: Minimizing the Number of Successor States in the Stubborn Set Method, Fundamenta Informaticae, 51(1–2), 2002, 215-234.