A geometrical method in combinatorial complexity
Applications of Mathematics, Tome 26 (1981) no. 2, pp. 82-96.

Voir la notice de l'article dans Czech Digital Mathematics Library

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
Mots-clés : 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},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {1981},
     doi = {10.21136/AM.1981.103900},
     mrnumber = {0612666},
     zbl = {0454.68028},
     language = {en},
     url = {https://geodesic-test.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
PB  - mathdoc
UR  - https://geodesic-test.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
%I mathdoc
%U https://geodesic-test.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. https://geodesic-test.mathdoc.fr/articles/10.21136/AM.1981.103900/

Cité par Sources :