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) Zbl0302.68010MR0445948
  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.

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.