中文

Operations Research Transactions >

2017 , Vol. 21 >Issue 2: 39 - 45

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2017.02.005

Complexity concepts for combinatorial and continuous optimization problems

Expand
  • 1. Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Received date: 2017-04-04

  Online published: 2017-06-15

Fold

Abstract

 Complexity concepts oriented from the theoretical Turing machine are widely accepted in study of combinatorial optimization problems. The polynomially computable and NP-hard concepts are frequently used in recent papers on continuous optimization problems. This paper presents a very brief introduction to show their relationship and difference used in the two fields.

Key words： complexity concepts; combinatorial optimization; continuous optimization

Cite this article

XING Wenxun . Complexity concepts for combinatorial and continuous optimization problems[J]. Operations Research Transactions, 2017 , 21(2) : 39 -45 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.02.005

References

[1] Cook S A. The complexity of theorem-proving procedures[C]//ACM Symposium on Theory of Computing,  Ohio: Shaker Heights, 1971, 151-158.
[2] Karmarkar N. A new polynomial-time algorithm for linear programming [J]. Combinatorica, 1984, 4: 373-395.
[3] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. San Francisco: W. H. Freeman and Company, 1979.
[4] Blum L, Shub M, Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines [J]. Bulletin of the American Mathematical Society, 1989, 21(1): 1-46.
[5] Nemirovski A S, Yudin D B. Problem Complexity and Method Efficiency in Optimization [M]. New York: Wiley-Interscience,  1983.
[6] Vavasis S A. Nonlinear Optimization: Complexity Issues [M]. New York: Oxford University Press, 1991.
[7] Frenk H, Roos K, Terlaky T, et al. High Performance Optimization [M]. New York: Springer, 1999.
[8] 方述诚, 邢文训. 线性锥优化 [M]. 北京: 科学出版社, 2013.
[9] Pardalos P M, Vavasis S A. Quadratic programming with one negative eigenvalue is NP-hard [J]. Journal of Global Optimization, 1991, 1(1): 15-22.
[10] 邢文训, 谢金星. 现代优化计算方法 [M]. 北京: 清华大学出版社, 2005.
Options
Outlines

/

〈 〉