The Art Gallery Guardian

Computing the weighted h-index


A common algorithm problem is that given a sequence of numbers, find a h-index. Where h-index is the largest integer such there are at least integers in the sequence is at least as large as .

Formally, we have the following problem.

Problem1

Given , find the largest , such that .

The h-index problem is featured in leetcode.

If we the numbers are sorted, then a trivial time algorithm exists. If it is not sorted, then note that we can solve the problem on . In this case, the input numbers is at most , therefore can be sorted in time. Hence the total running time is .

Consider a weighted version of the problem where the above algorithm does not work.

Problem2

Given a sequence of pairs of non-negative positive reals . Find the largest , such that .

An time algorithm still exists. For simplicity, we assume all ’s are distinct, so the input is a set. The case where ’s are not distinct is left as an exercise to the reader.

Define . We want to find the largest such that . First, we can find the median of , say . If , then we recurse on . Assume the optimum in the recursed solution is , we return as the solution. If , then we recurse and output the solution with input . The running time satisfies , which is .

Posted by Chao Xu on .
Tags: algorithms.