HomeIssuesComputational complexity of the synthesis of composite models for Lipschitz-bounded functions

Computational complexity of the synthesis of composite models for Lipschitz-bounded functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 3 (25).

The paper is devoted to the analysis of computational complexity of the synthesis of composite models for Lipschitz-bounded surjective functions of single variable. Composite models are some function approximation methods based on approximating via composition of functions taken from a given set. In this paper, it is proved that the problem of building strictly optimal composite model for a target functions via a given set of functions is NP-complete. Methods that are capable to build a near-optimal composition model are discussed. Some of these methods can be realized as algorithms with the polynomial computational complexity but they have a limited application.
Download file
Counter downloads: 66
  • Title Computational complexity of the synthesis of composite models for Lipschitz-bounded functions
  • Headline Computational complexity of the synthesis of composite models for Lipschitz-bounded functions
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3 (25)
  • Date:
  • DOI
Keywords
композиционные модели, композиция функций, NP-полнота, липшиц-ограниченность, вычислительная сложность, function composition, composition models, NP-completeness, Lipschitz-bounded, computational complexity
Authors
References
Alenberg L. The schema theorem and Price's theorem // Foundations of Genetic Algorithms 3. San Francisco: Morgan Kaufmann, 1995. P. 23-49.
Zezula P., Amato G., Dohnal V., and Batko M. Similarity Search: The Metric Space Approach. N. Y.: Springer Verlag, 2006. 220 p.
Растригин Л. А., Рипа К. К, Тарасенко Г. С. Адаптация случайного поиска. Рига: Зи-натне, 1978. 243 с.
Chavez E., Navarro G., Baeza-Yates R., and Marroquin J. L. Search in metric spaces // ACM Computing Surveys. 2001. V.33. No. 3. P. 273-321.
Калинников И. С. Алгоритм построения декомпозиции непрерывной функции одного аргумента по заданному множеству функций // Инновации в науке, образовании и бизнесе: Х Междунар. научн. конф. Калининград: КГТУ, 2012. Ч.2. С. 160-163.
Alonso C., Gutierrez J., and Recio T. A rational function decomposition algorithm by near-separated polynomials // J. Symbolic Comput. 1995. V. 19. P. 527-544.
Even S. and Goldreich O. The minimum-length generator sequence problem is NP-hard // J. Algorithms. 1981. No. 2. P. 311-313.
Пападимитриу X. X., Стайглиц . Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1987. 520 с.
Karp R.M. Reducibility among combinatorial problems // GJ-474 report. 1971. P. 87-103. http://www.seas.upenn.edu/~bhusnur4/cit596_spring2014/karp-1971.pdf
Seong J. K., Elber G., and Kim M. S. Polynomial decomposition and its applications. http: //cana.kaist.ac.kr/seong/decomposition.pdf. 2003.
Luke S. Essentials of metaheuristics. http://cs.gmu.edu/~sean/book/metaheuristics. 2009.
Лабутин С. А., Пугин М. В. Анализ сигналов и зависимостей: учеб. пособие. Н.Новгород: Нижегород. гос. тех. ун-т, 2001. 158с.
Koza J. R. Genetic Programming: on the Programming of Computers by Means of Natural Selection. London: A Bradford Book, 1998. 815 p.
Computational complexity of the synthesis of composite models for Lipschitz-bounded functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 3 (25).
Computational complexity of the synthesis of composite models for Lipschitz-bounded functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 3 (25).
Download full-text version
Counter downloads: 168