Complexity of some parametric integer and network programming problems |
| |
Authors: | Patricia J Carstensen |
| |
Institution: | (1) Department of Mathematics, University of Michigan, Ann Arbor, MI, USA |
| |
Abstract: | Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given;
in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables
in the problem.
This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646 |
| |
Keywords: | Parametric Programming 0-1 Programming Network Programming Complexity |
本文献已被 SpringerLink 等数据库收录! |