On a Class of Optimization Problems with No “Efficiently Computable” Solution
- Авторлар: Gavrilovich M.1, Kreps V.1
-
Мекемелер:
- National Research University Higher School of Economics
- Шығарылым: Том 215, № 6 (2016)
- Беттер: 706-714
- Бөлім: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/237708
- DOI: https://doi.org/10.1007/s10958-016-2876-0
- ID: 237708
Дәйексөз келтіру
Аннотация
It is well known that large random structures may have nonrandom macroscopic properties. We give an example of nonrandom properties for a class of large optimization problems related to the computational problem MAXFLS= of calculating the maximum number of consistent equations in a given overdetermined system of linear equations. A problem of this kind is faced by a decision maker (an Agent) choosing means to protect a house from natural disasters. For this class we establish the following. There is no “efficiently computable” optimal strategy of the Agent. As the size of a random instance of the optimization problem goes to infinity, the probability that the uniform mixed strategy of the Agent is ε-optimal goes to one. Moreover, there is no “efficiently computable” strategy of the Agent that is substantially better for each instance of the optimization problem. Bibliography: 13 titles.
Негізгі сөздер
Авторлар туралы
M. Gavrilovich
National Research University Higher School of Economics
Хат алмасуға жауапты Автор.
Email: mishap@sdf.org
Ресей, St.Petersburg
V. Kreps
National Research University Higher School of Economics
Email: mishap@sdf.org
Ресей, St.Petersburg