A randomized in-place algorith for positioning the k\'th element in a multiset

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

A randomized in-place algorith for positioning the k\'th element in a multiset. / Katajainen, Jyrki; Pasanen, Tomi A.

Proceedings of the 8th Scandinavian Workshop on Algorithm Theory. Springer, 2002. p. 408-417.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Katajainen, J & Pasanen, TA 2002, A randomized in-place algorith for positioning the k\'th element in a multiset. in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory. Springer, pp. 408-417, A randomized in-place algorith for positioning the k\'th element in a multiset, 29/11/2010.

APA

Katajainen, J., & Pasanen, T. A. (2002). A randomized in-place algorith for positioning the k\'th element in a multiset. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (pp. 408-417). Springer.

Vancouver

Katajainen J, Pasanen TA. A randomized in-place algorith for positioning the k\'th element in a multiset. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory. Springer. 2002. p. 408-417

Author

Katajainen, Jyrki ; Pasanen, Tomi A. / A randomized in-place algorith for positioning the k\'th element in a multiset. Proceedings of the 8th Scandinavian Workshop on Algorithm Theory. Springer, 2002. pp. 408-417

Bibtex

@inproceedings{95793dc0c46711debda0000ea68e967b,
title = "A randomized in-place algorith for positioning the k\'th element in a multiset",
abstract = "A variant of the classical selection problem, called the positioning problem, is considered. In this problem we are given a sequence A[1:n] of size n, an integer k, 1 = k = n, and an ordering function  ¿< , and the task is to rearrange the elements of the sequence such that A[k]  ¿<  A[j] is false for all j, 1 = j < k, and A[l]  ¿<  A[k] is false for all l, k < l = n. We present a Las-Vegas algorithm which carries out this rearrangement efficiently using only a constant amount of additional space even if the input contains equal elements and if only pairwise element comparisons are permitted. To be more precise, the algorithm solves the positioning problem in-place in linear time using at most n + k + o(n) element comparisons, k + o(n) element exchanges, and the probability for succeeding within stated time bounds is at least 1-e-nO(1).",
author = "Jyrki Katajainen and Pasanen, {Tomi A.}",
year = "2002",
language = "English",
pages = "408--417",
booktitle = "Proceedings of the 8th Scandinavian Workshop on Algorithm Theory",
publisher = "Springer",
address = "Switzerland",
note = "A randomized in-place algorith for positioning the k\'th element in a multiset ; Conference date: 29-11-2010",

}

RIS

TY - GEN

T1 - A randomized in-place algorith for positioning the k\'th element in a multiset

AU - Katajainen, Jyrki

AU - Pasanen, Tomi A.

PY - 2002

Y1 - 2002

N2 - A variant of the classical selection problem, called the positioning problem, is considered. In this problem we are given a sequence A[1:n] of size n, an integer k, 1 = k = n, and an ordering function  ¿< , and the task is to rearrange the elements of the sequence such that A[k]  ¿<  A[j] is false for all j, 1 = j < k, and A[l]  ¿<  A[k] is false for all l, k < l = n. We present a Las-Vegas algorithm which carries out this rearrangement efficiently using only a constant amount of additional space even if the input contains equal elements and if only pairwise element comparisons are permitted. To be more precise, the algorithm solves the positioning problem in-place in linear time using at most n + k + o(n) element comparisons, k + o(n) element exchanges, and the probability for succeeding within stated time bounds is at least 1-e-nO(1).

AB - A variant of the classical selection problem, called the positioning problem, is considered. In this problem we are given a sequence A[1:n] of size n, an integer k, 1 = k = n, and an ordering function  ¿< , and the task is to rearrange the elements of the sequence such that A[k]  ¿<  A[j] is false for all j, 1 = j < k, and A[l]  ¿<  A[k] is false for all l, k < l = n. We present a Las-Vegas algorithm which carries out this rearrangement efficiently using only a constant amount of additional space even if the input contains equal elements and if only pairwise element comparisons are permitted. To be more precise, the algorithm solves the positioning problem in-place in linear time using at most n + k + o(n) element comparisons, k + o(n) element exchanges, and the probability for succeeding within stated time bounds is at least 1-e-nO(1).

M3 - Article in proceedings

SP - 408

EP - 417

BT - Proceedings of the 8th Scandinavian Workshop on Algorithm Theory

PB - Springer

T2 - A randomized in-place algorith for positioning the k\'th element in a multiset

Y2 - 29 November 2010

ER -

ID: 15431055