Min-Max Optimization of Several Classical Discrete Optimization Problems |
| |
| Authors: | G Yu |
| |
| Institution: | (1) Department of Management Science and Information Systems, Graduate School of Business and Center for Management of Operations and Logistics, University of Texas at Austin, Austin, Texas |
| |
| Abstract: | In this paper, we study discrete optimization problems with min-max objective functions. This type of problems has direct applications in the recent development of robust optimization. The following well-known classes of problems are discussed: minimum spanning tree problem, resource allocation problem with separable cost functions, and production control problem. Computational complexities of the corresponding min-max version of the above-mentioned problems are analyzed. Pseudopolynomial algorithms for these problems are provided under certain conditions. |
| |
| Keywords: | Min-max discrete optimization computational complexity pseudopolynomial algorithms |
| 本文献已被 SpringerLink 等数据库收录！ |
|
