| Title:
|
On the conjecture relating minimax and minimean complexity norms (English) |
| Author:
|
Růžička, Peter |
| Author:
|
Wiedermann, Juraj |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
24 |
| Issue:
|
5 |
| Year:
|
1979 |
| Pages:
|
321-325 |
| Summary lang:
|
English |
| Summary lang:
|
Slovak |
| Summary lang:
|
Russian |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
minimax and minimean complexity |
| Keyword:
|
optimal algorithm |
| Keyword:
|
uniform complexity |
| MSC:
|
68C25 |
| MSC:
|
68Q25 |
| MSC:
|
68W99 |
| idZBL:
|
Zbl 0434.68029 |
| idMR:
|
MR0547036 |
| DOI:
|
10.21136/AM.1979.103813 |
| . |
| Date available:
|
2008-05-20T18:12:32Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103813 |
| . |
| Reference:
|
[1] D. E. Knuth: The Art of Computer Programming. Volume 3. Sorting and Searching.Addison-Wesley. 1973. MR 0445948 |
| Reference:
|
[2] I. Pohl: Minimean Optimality in Sorting Algorithms.Proceedings of 16th Annual Symposium on Foundations of Computer Science. 1975, 71 - 74. MR 0433968 |
| Reference:
|
[3] I. Pohl: On Selection over Six Elements and a Conjecture Relating Two Complexity Norms.Vrije Universiteit. Wiskundik Seminarium. Amsterdam. March 1975. |
| . |
