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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D. Gusfield, “Sensitivity analysis for combinatorial optimization”, Memorandum number UCB/ERL M80/22, Electronics Research Laboratory (Berkeley, CA, 1980).
O.H. Ibarra and C.E. Kim, “Fast approximation algorithms for the knapsack and sum of subset problem”,Journal of the Association for Computing Machinery 22 (1975) 463–468.
V. Klee and G.J. Minty, “How good is the simplex algorithm?”, in O. Shisha, Ed.,Inequalities III (Academic Press, New York, 1969) pp. 159–175.
G. Mathews, “On the partition of numbers”,Proceedings of the London Mathematical Society 28 (1897) 486–490.
K. Murty, “Computational complexity of parametric linear programming”,Mathematical Programming 19 (1980) 213–219.
R. Rockafellar,Convex analysis (Princeton University Press, Princeton, NJ, 1970).
I.G. Rosenberg, “Aggregation of equations in integer programming,“Discrete Mathematics 10 (1974) 325–341.
H. Stone, “Multiprocessor scheduling with aid ne.work flow algorithms”,IEEE Transactions on Software Engineering SE-3 (1977) 85–93.
H. Stone, “Critical load factors”,IEEE Transactions on Software Engineering SE-4 (1978) 254–258.
N. Zadeh, “A bad network problem for the simplex method and other minimum cost flow algorithms”,Mathematical Programming 5 (1973) 255–266.
Author information
Authors and Affiliations
Additional information
This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646
Rights and permissions
About this article
Cite this article
Carstensen, P.J. Complexity of some parametric integer and network programming problems. Mathematical Programming 26, 64–75 (1983). https://doi.org/10.1007/BF02591893
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591893