On the conjecture relating minimax and minimean complexity norms

Peter Růžička; Juraj Wiedermann

Aplikace matematiky (1979)

  • Volume: 24, Issue: 5, page 321-325
  • ISSN: 0862-7940

Abstract

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

How to cite

top

Růžička, Peter, and Wiedermann, Juraj. "On the conjecture relating minimax and minimean complexity norms." Aplikace matematiky 24.5 (1979): 321-325. <http://eudml.org/doc/15109>.

@article{Růžička1979,
abstract = {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.},
author = {Růžička, Peter, Wiedermann, Juraj},
journal = {Aplikace matematiky},
keywords = {minimax and minimean complexity; optimal algorithm; uniform complexity; minimax and minimean complexity; optimal algorithm; uniform complexity},
language = {eng},
number = {5},
pages = {321-325},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the conjecture relating minimax and minimean complexity norms},
url = {http://eudml.org/doc/15109},
volume = {24},
year = {1979},
}

TY - JOUR
AU - Růžička, Peter
AU - Wiedermann, Juraj
TI - On the conjecture relating minimax and minimean complexity norms
JO - Aplikace matematiky
PY - 1979
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 24
IS - 5
SP - 321
EP - 325
AB - 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.
LA - eng
KW - minimax and minimean complexity; optimal algorithm; uniform complexity; minimax and minimean complexity; optimal algorithm; uniform complexity
UR - http://eudml.org/doc/15109
ER -

References

top
  1. D. E. Knuth, The Art of Computer Programming. Volume 3. Sorting and Searching, Addison-Wesley. 1973. (1973) MR0445948
  2. I. Pohl, Minimean Optimality in Sorting Algorithms, Proceedings of 16th Annual Symposium on Foundations of Computer Science. 1975, 71 - 74. (1975) MR0433968
  3. I. Pohl, On Selection over Six Elements and a Conjecture Relating Two Complexity Norms, Vrije Universiteit. Wiskundik Seminarium. Amsterdam. March 1975. (1975) 

NotesEmbed ?

top

You must be logged in to post comments.