Date: 09 Apr 2002
From: jyrki@diku.dk
Subject: A randomized in-place algorithm for positioning the k'th element

Title: A randomized in-place algorithm for positioning the k'th element
in  a multiset

Speaker: Jyrki Katajainen

Time:  Monday, 15 April 2002, 13.15–14.00
Place: N034 at DIKU

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 \le k \le n$, and a strict
weak ordering $\less$, and the task is to rearrange the elements of the
sequence in such way that $A[k] \less A[j]$ is false for all $j$,
$1 \le j < k$, and $A[l] \less A[k]$ is false for all $l$, $k < l \le 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^{-n^{\Omega(1)}}$.

(Joint work with Tomi Pasanen)

To be presented at the 8th Scandinavian Workshop on Algorithm Theory,
which will be held on 3–5 July 2002 in Turku, Finland.

The talk is part of the M.Sc. seminar led by Jyrki Katajainen, but
anyone interested is welcome to attend.

Seminar homepage:  http://www.diku.dk/undervisning/2002f/741/
PE-lab's homepage: http://www.diku.dk/~jyrki/PE-lab/