Geodesic
On the conjecture relating minimax and minimean complexity norms
Applications of Mathematics, Tome 24 (1979) no. 5, pp. 321-325
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Using counterexample it has been shown that an algorithm which is minimax optimal and over all minimax optimal algorithms is minimean optimal and has a uniform behaviour need not to be minimean optimal.
Using counterexample it has been shown that an algorithm which is minimax optimal and over all minimax optimal algorithms is minimean optimal and has a uniform behaviour need not to be minimean optimal.
DOI : 10.21136/AM.1979.103813
Classification : 68C25, 68Q25, 68W99
Keywords: minimax and minimean complexity; optimal algorithm; uniform complexity 
@article{10_21136_AM_1979_103813,
     author = {R\r{u}\v{z}i\v{c}ka, Peter and Wiedermann, Juraj},
     title = {On the conjecture relating minimax and minimean complexity norms},
     journal = {Applications of Mathematics},
     pages = {321--325},
     year = {1979},
     volume = {24},
     number = {5},
     doi = {10.21136/AM.1979.103813},
     mrnumber = {0547036},
     zbl = {0434.68029},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1979.103813/}
}
TY  - JOUR
AU  - Růžička, Peter
AU  - Wiedermann, Juraj
TI  - On the conjecture relating minimax and minimean complexity norms
JO  - Applications of Mathematics
PY  - 1979
SP  - 321
EP  - 325
VL  - 24
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1979.103813/
DO  - 10.21136/AM.1979.103813
LA  - en
ID  - 10_21136_AM_1979_103813
ER  - 
%0 Journal Article
%A Růžička, Peter
%A Wiedermann, Juraj
%T On the conjecture relating minimax and minimean complexity norms
%J Applications of Mathematics
%D 1979
%P 321-325
%V 24
%N 5
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1979.103813/
%R 10.21136/AM.1979.103813
%G en
%F 10_21136_AM_1979_103813
Růžička, Peter; Wiedermann, Juraj. On the conjecture relating minimax and minimean complexity norms. Applications of Mathematics, Tome 24 (1979) no. 5, pp. 321-325. doi: 10.21136/AM.1979.103813

[1] D. E. Knuth: The Art of Computer Programming. Volume 3. Sorting and Searching. Addison-Wesley. 1973. | MR

[2] I. Pohl: Minimean Optimality in Sorting Algorithms. Proceedings of 16th Annual Symposium on Foundations of Computer Science. 1975, 71 - 74. | MR

[3] I. Pohl: On Selection over Six Elements and a Conjecture Relating Two Complexity Norms. Vrije Universiteit. Wiskundik Seminarium. Amsterdam. March 1975.

Cité par Sources :