<p>I have to implement an algorithm that solves the multi-selection problem.
The multiselection problem is:</p>

<blockquote>
  <p>Given a set S of n elements drawn from a linearly ordered set, and a set $K = {k_{1}, &gt;k_{2},...,k_{r}}$ of positive integers between 1 and n, the multiselection problem is to >select the $k_{i}th$ smallest element for all values of i, $1 \le i \le r$</p>
</blockquote>

<p>I need to solve the average case on $ \theta(n log p) $.
I've found a paper that implements the solution I need, but it assumes that there are no repeated numbers on the set S. The problem is that I can't assume that and I don't know how to adapt the algorithm of that paper to support repeated numbers.
The paper is here: <a href="http://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf" rel="nofollow">http://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf</a> 
and the algorithm is on the second page. Any tips are welcome!</p>

CC BY-SA 3.0
2013-09-30T06:42:23.913Z
Please proof-read your question.  It appears that you have some editing issues (e.g., stray `>`'s have crept in) and some sub-optimal use of Latex.  Also, what is $p$?  The parameter $p$ is not defined anywhere.  Do you mean $\Theta(n \lg r)$?
D.W.
CC BY-SA 3.0
2013-09-30T15:07:31.263Z
Checkout ESA 2013 proceedings for the paper "Theory and Implementation of Online Multiselection Algorithms", by me and my coauthors.
J.y B.y
<selection>
Efficient multi-selection algorithm
Ivan
# Efficient multi-selection algorithm

(Asked by: username_0 on 2013-09-29)

I have to implement an algorithm that solves the multi-selection problem.
The multiselection problem is:

> Given a set S of n elements drawn from a linearly ordered set, and a set $K = {k\_{1}, >k\_{2},...,k\_{r}}$ of positive integers between 1 and n, the multiselection problem is to >select the $k\_{i}th$ smallest element for all values of i, $1 \le i \le r$

I need to solve the average case on $ \theta(n log p) $.
I've found a paper that implements the solution I need, but it assumes that there are no repeated numbers on the set S. The problem is that I can't assume that and I don't know how to adapt the algorithm of that paper to support repeated numbers.
The paper is here: <http://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf>
and the algorithm is on the second page. Any tips are welcome!

**Tags:** selection
> **Comments:**
> **username_1**: Please proof-read your question.  It appears that you have some editing issues (e.g., stray `>`'s have crept in) and some sub-optimal use of Latex.  Also, what is $p$?  The parameter $p$ is not defined anywhere.  Do you mean $\Theta(n \lg r)$?  
> **username_2**: Checkout ESA 2013 proceedings for the paper "Theory and Implementation of Online Multiselection Algorithms", by me and my coauthors.  

---

## 0 answers

