Geodesic
A geometrical method in combinatorial complexity
Applications of Mathematics, Tome 26 (1981) no. 2, pp. 82-96
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/AM.1981.103900
Classification : 52A37, 68C25, 68Q25, 90C10
Keywords: lower bound for the number of comparisons; knapsack problem; decomposition of polyhedral sets into convex sets 
@article{10_21136_AM_1981_103900,
     author = {Mor\'avek, Jaroslav},
     title = {A geometrical method in combinatorial complexity},
     journal = {Applications of Mathematics},
     pages = {82--96},
     year = {1981},
     volume = {26},
     number = {2},
     doi = {10.21136/AM.1981.103900},
     mrnumber = {0612666},
     zbl = {0454.68028},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1981.103900/}
}
TY  - JOUR
AU  - Morávek, Jaroslav
TI  - A geometrical method in combinatorial complexity
JO  - Applications of Mathematics
PY  - 1981
SP  - 82
EP  - 96
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1981.103900/
DO  - 10.21136/AM.1981.103900
LA  - en
ID  - 10_21136_AM_1981_103900
ER  - 
%0 Journal Article
%A Morávek, Jaroslav
%T A geometrical method in combinatorial complexity
%J Applications of Mathematics
%D 1981
%P 82-96
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1981.103900/
%R 10.21136/AM.1981.103900
%G en
%F 10_21136_AM_1981_103900
Morávek, Jaroslav. A geometrical method in combinatorial complexity. Applications of Mathematics, Tome 26 (1981) no. 2, pp. 82-96. doi: 10.21136/AM.1981.103900

[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

[3] J. Morávek: A Note upon Minimal Path Problem. Journal of Math. Analysis and Appl., 30 (1970) 3, pp. 702-717. | DOI | MR

[4] J. Morávek: A Localization Problem in Geometry and Complexity of Discrete Programming. Kybernetika, 8 (1972) 6, pp. 498-516. | MR

[5] S. Muroga: Threshold Logic and Its Applications. John Wiley & Sons, New York, London, Sydney, 1971. | MR | Zbl

[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 | Zbl

[8] R. M. Karp: Reducibility among Combinatorial Problems. Complexity of Computer Computations, Proceedings, Plenum Press 1972. Editors: R. E. Miller, J. W. Thatcher. | DOI | MR

[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

[10] M. Blum R. W. Floyd V. Pratt R. Rivest, R. Tarjan: Time Bounds for Selection. JCSS 7 (1973), pp. 448-461. | MR

[11] J. Pohl: A Sorting Problem and Its Complexity. Communications of ACM, 15 (1972) 6, pp. 462-466. | DOI | Zbl

[12] R. E. Bellman: Dynamic Programming Treatment of the Travelling Salesman Problem. J. Assoc. for Соmр. Mach. 9 (1962), pp. 61-63. | DOI | MR | Zbl

[13] M. Held, R. M. Karp: A Dynamic Programming Approach to Sequencing Problems. J. Soc. Ind. and Appl. Math. 10 (1962) 1. | DOI | MR | Zbl

[14] А. А. Корбут Ю. Ю. Финкелъштейи: Дискретное программирование. Москва, Наука 1969. | Zbl

[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

[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

Cité par Sources :