A geometrical method in combinatorial complexity

Jaroslav Morávek

Aplikace matematiky (1981)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.