# A geometrical method in combinatorial complexity

Aplikace matematiky (1981)

- Volume: 26, Issue: 2, page 82-96
- ISSN: 0862-7940

## Access Full Article

top## Abstract

top## How to cite

topMorávek, Jaroslav. "A geometrical method in combinatorial complexity." Aplikace matematiky 26.2 (1981): 82-96. <http://eudml.org/doc/15185>.

@article{Morávek1981,

abstract = {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.},

author = {Morávek, Jaroslav},

journal = {Aplikace matematiky},

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},

language = {eng},

number = {2},

pages = {82-96},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {A geometrical method in combinatorial complexity},

url = {http://eudml.org/doc/15185},

volume = {26},

year = {1981},

}

TY - JOUR

AU - Morávek, Jaroslav

TI - A geometrical method in combinatorial complexity

JO - Aplikace matematiky

PY - 1981

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 26

IS - 2

SP - 82

EP - 96

AB - 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.

LA - eng

KW - 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

UR - http://eudml.org/doc/15185

ER -

## References

top- J. Morávek, On the Complexity of Discrete Programming Problems, The talk on the 6th International Symposium on Mathematical Programming, Princeton University 1967. (1967) Zbl0196.22804
- J. Morávek, On the Complexity of Discrete Programming Problems, Aplikace Matematiky, 14 (1969), pp. 442-474. (1969) Zbl0196.22804MR0253745
- J. Morávek, 10.1016/0022-247X(70)90154-X, Journal of Math. Analysis and Appl., 30 (1970) 3, pp. 702-717. (1970) Zbl0175.17703MR0278984DOI10.1016/0022-247X(70)90154-X
- J. Morávek, A Localization Problem in Geometry and Complexity of Discrete Programming, Kybernetika, 8 (1972) 6, pp. 498-516. (1972) Zbl0248.90044MR0395873
- S. Muroga, Threshold Logic and Its Applications, John Wiley & Sons, New York, London, Sydney, 1971. (1971) Zbl0243.94014MR0439441
- 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. (1976) Zbl0362.68077
- J. L. Kelley, General Topology, Van Nostrand Reinhold Company, 1955. (1955) Zbl0066.16604MR0070144
- R. M. Karp, 10.1007/978-1-4684-2001-2_9, Complexity of Computer Computations, Proceedings, Plenum Press 1972. Editors: R. E. Miller, J. W. Thatcher. (1972) Zbl0366.68041MR0378476DOI10.1007/978-1-4684-2001-2_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. MR0164907
- M. Blum R. W. Floyd V. Pratt R. Rivest, R. Tarjan, Time Bounds for Selection, JCSS 7 (1973), pp. 448-461. (1973) Zbl0278.68033MR0329916
- J. Pohl, 10.1145/361405.361423, Communications of ACM, 15 (1972) 6, pp. 462-466. (1972) Zbl0234.68020DOI10.1145/361405.361423
- R. E. Bellman, 10.1145/321105.321111, J. Assoc. for Соmр. Mach. 9 (1962), pp. 61-63. (1962) Zbl0106.14102MR0135702DOI10.1145/321105.321111
- M. Held, R. M. Karp, 10.1137/0110015, J. Soc. Ind. and Appl. Math. 10 (1962) 1. (1962) Zbl0106.14103MR0139493DOI10.1137/0110015
- А. А. Корбут Ю. Ю. Финкелъштейи, Дискретное программирование, Москва, Наука 1969. (1969) Zbl1231.90028
- R. О. Winder, Bounds of Threshold Gate Realizability, TRNS IEEE EC 12 (1963). (1963) Zbl0203.15702
- S. Yajima, T. Ibaraki, A Lower Bound of the Number of Threshold Functions, TRNS IEEE EC 14 (1965) 6. (1965) Zbl0197.43606
- M. Block, J. Morávek, Bounds of the Number of Threshold Functions, Informations Processing Machines, 13 (1967), pp. 67-73. (1967)
- 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. (1978) Zbl0397.68045MR0496639

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.