×
Morávek, Jaroslav

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

Apl. Mat. 14, 442-474 (1969).
Reviewer: Jaroslav Morávek
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0196.22804

Cited in 3 Documents

MSC:

90C10 Integer programming
90C60 Abstract computational complexity for mathematical programming problems
90C09 Boolean programming
90C27 Combinatorial optimization
90C39 Dynamic programming

Keywords:

algorithmic complexity; discrete integer programming; linear-separating algorithms; L-S algorithm; lower bounds; number of comparisons; complexity indices
PDF BibTeX XML Cite
\textit{J. Morávek}, Apl. Mat. 14, 442--474 (1969; Zbl 0196.22804)
Full Text: EuDML
  • logo of hbz
  • logo of WorldCat

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.