Article
Full entry |
PDF
(1.5 MB)
Feedback
PDF
(1.5 MB)
Feedback
Keywords:
lower bound for the number of comparisons; knapsack problem; decomposition of polyhedral sets into convex sets
lower bound for the number of comparisons; knapsack problem; decomposition of polyhedral sets into convex sets
Summary:
A lower bound for the number of comparisons is obtained, required by a computational problem of classification of an arbitrarily chosen point of the Euclidean space with respect to a given finite family of polyhedral (non-convex, in general) sets, covering the space. This lower bound depends, roughly speaking, on the minimum number of convex parts, into which one can decompose these polyhedral sets. The lower bound is then applied to the knapsack problem.
References:
[1] J. Morávek: On the Complexity of Discrete Programming Problems. The talk on the 6th International Symposium on Mathematical Programming, Princeton University 1967.
[2] J. Morávek: On the Complexity of Discrete Programming Problems. Aplikace Matematiky, 14 (1969), pp. 442-474. MR 0253745
[3] J. Morávek: A Note upon Minimal Path Problem. Journal of Math. Analysis and Appl., 30 (1970) 3, pp. 702-717. DOI 10.1016/0022-247X(70)90154-X | MR 0278984
[4] J. Morávek: A Localization Problem in Geometry and Complexity of Discrete Programming. Kybernetika, 8 (1972) 6, pp. 498-516. MR 0395873
[5] S. Muroga: Threshold Logic and Its Applications. John Wiley & Sons, New York, London, Sydney, 1971. MR 0439441 | Zbl 0243.94014
[6] D. Dobkin, R. J. Lipton: A Lower Bound of $\frac{1}{2} n^2$ on Linear Search Programs for the Knapsack Problem. Mathematical Foundations of Computer Science 1976, Gdansk, published in Lecture Notes in Computer Science 45, 1976.
[7] J. L. Kelley: General Topology. Van Nostrand Reinhold Company, 1955. MR 0070144 | Zbl 0066.16604
[8] R. M. Karp: Reducibility among Combinatorial Problems. Complexity of Computer Computations, Proceedings, Plenum Press 1972. Editors: R. E. Miller, J. W. Thatcher. DOI 10.1007/978-1-4684-2001-2_9 | MR 0378476
[9] S. S. Kislicyn: On the Selection of the k-th Element of an Ordered Set by Pairwise Comparisons. (Russian), Sibirsk. Mat. Zh., Vol. 5, pp. 557-564. MR 0164907
[10] M. Blum R. W. Floyd V. Pratt R. Rivest, R. Tarjan: Time Bounds for Selection. JCSS 7 (1973), pp. 448-461. MR 0329916
[11] J. Pohl: A Sorting Problem and Its Complexity. Communications of ACM, 15 (1972) 6, pp. 462-466. DOI 10.1145/361405.361423 | Zbl 0234.68020
[12] R. E. Bellman: Dynamic Programming Treatment of the Travelling Salesman Problem. J. Assoc. for Соmр. Mach. 9 (1962), pp. 61-63. DOI 10.1145/321105.321111 | MR 0135702 | Zbl 0106.14102
[13] M. Held, R. M. Karp: A Dynamic Programming Approach to Sequencing Problems. J. Soc. Ind. and Appl. Math. 10 (1962) 1. DOI 10.1137/0110015 | MR 0139493 | Zbl 0106.14103
[14] А. А. Корбут Ю. Ю. Финкелъштейи: Дискретное программирование. Москва, Наука 1969. Zbl 1231.90028
[15] R. О. Winder: Bounds of Threshold Gate Realizability. TRNS IEEE EC 12 (1963).
[16] S. Yajima, T. Ibaraki: A Lower Bound of the Number of Threshold Functions. TRNS IEEE EC 14 (1965) 6. Zbl 0197.43606
[17] M. Block, J. Morávek: Bounds of the Number of Threshold Functions. Informations Processing Machines, 13 (1967), pp. 67-73.
[18] D. Dobkin, R. J. Lipton: A Lower Bound of $\frac{1}{2} n^2$ on Linear Search Programs for the Knapsack Problem. JCSS, 16 (1978) 3, pp. 413-417. MR 0496639
Search
Partner of
