×

On the complexity of discrete programming problems. (English) Zbl 0196.22804


MSC:

90C10 Integer programming
90C60 Abstract computational complexity for mathematical programming problems
90C09 Boolean programming
90C27 Combinatorial optimization
90C39 Dynamic programming
PDF BibTeX XML Cite
Full Text: EuDML

References:

[1] Коробков В. К.: О некоторых целочисленных задачах линейного программирования. Проблемы кибернетики, том 14, Москва 1965. · Zbl 1099.01519
[2] Balas E.: An Additive Algorithm for Solving Linear Programs with 0- 1 Variables. Opns. Res. 13, 517-549, 1965. · Zbl 0194.19903
[3] Bloch M., Morávek J.: Bounds of the number of threshold functions. Information Processing Machines, Praha 1967.
[4] Winder R. O.: Bounds of threshold gate readability. TRNS IEEE EC - 12, Oct. 63. · Zbl 0139.11801
[5] Нечипорук Є. И.: О синтезе схем из пороговых элементов. Проблемы кибернетики. tom 11, Москва 1964. · Zbl 1117.65300
[6] Goldman A. J., Tucker A. W.: Polyhedral Convex Cones, Linear Inequalities and Related Systems. Princeton 1956. · Zbl 0072.37504
[7] Ford L. R., Fulkerson D. R.: Flows in Networks. Princeton 1962. · Zbl 0106.34802
[8] Bellman R. E.: Dynamic Programming Treatment of the Travelling Salesman Problem. J. Assoc. for Comp. Mach. 9, 61 - 63 (1962). · Zbl 0106.14102
[9] Little J. D. C., Murty K. G., Sweeney D. W., and Karel C.: An Algorithm for the Travelling Salesman Problem. Opns. Res. 11, 972-989, 1963. · Zbl 0161.39305
[10] Vlach M.: Řešení dopravního problému metodou větvení. Ekonomicko-matematický obzor, 2, N. 4, 1966.
[11] Yajima S., Ibaraki T.: A lower Bound of the Number of Threshold Functions. IEEE, EC Dec. 1965, Vol. 14, N. 6. · Zbl 0197.43606
[12] Morávek J.: О некоторых оценках для пороговых функций. Term paper, Leningrad University, 1963.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.