Approximation and Complexity

Panos M. Pardalos, Antanas Žilinskas and Julius Žilinskas
Additional contact information
Panos M. Pardalos: University of Florida
Antanas Žilinskas: Vilnius University
Julius Žilinskas: Vilnius University

Chapter Chapter 3 in Non-Convex Multi-Objective Optimization, 2017, pp 19-31 from Springer

Abstract: Abstract In computer science, the theory of computational complexity was developed to evaluate the hardness of problems, regarding the number of steps to obtain a solution; for the basic results of that theory we refer to [147]. The model of computations, used in that theory, is either the Turing machine or any other equivalent model. The input and output of the Turing machine should be encoded as finite strings of bits. Such an encoding can be used to represent the objects of discrete nature, and the theory of computational complexity is favorable, e.g., to the investigation of problems of single-objective combinatorial optimization [150, 151]. However, the Turing machine model is not suitable for the algorithms using real numbers. Therefore alternative complexity theories have been developed for the investigation of problems of continuous nature. For the fundamentals of the complexity of real number algorithms we refer to [19, 218], and for the complexity of problems of mathematical programming to [143, 150, 151].

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-61007-8_3

Ordering information: This item can be ordered from
http://www.springer.com/9783319610078

DOI: 10.1007/978-3-319-61007-8_3

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().