离散优化与连续优化的复杂性概念

doi:10.15960/j.cnki.issn.1007-6093.2017.02.005

Operations Research Transactions

Previous Articles Next Articles

Complexity concepts for combinatorial and continuous optimization problems

XING Wenxun^1,*

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

Received:2017-04-04 Online:2017-06-15 Published:2017-06-15

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, doi: 10.15960/j.cnki.issn.1007-6093.2017.02.005.

share this article

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2017.02.005

https://www.ort.shu.edu.cn/EN/Y2017/V21/I2/39

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.

Metrics

Viewed

Full text

Abstract

Comments

Abstract
References
Related Articles
Recommended Articles
Metrics
Comments

TOP

Complexity concepts for combinatorial and continuous optimization problems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[2]	CHEN Xujin, XU Dachuan, ZHANG Guochuan. New perspectives of several fundamental problems in combinatorial optimization [J]. Operations Research Transactions, 2014, 18(1): 149-158.