Alex Rivera | Logout

Removing items from unevenly distributed set

Asked 2012-01-05T17:59:59.230
9

I have a website where users submit questions (zero, one or multiple per day), vote on them and answer one question per day (more details here). A user can see the question only once either by submitting, voting or answering it.

I have a pool of questions that players have already seen. I need to remove 30 questions from the pool each month. I need to pick questions to remove in such way that I maximize the number of available questions left in the pool for player with least available questions.

Example with pool of 5 questions (and need to remove 3):

  • player A has seen questions 1, 3 and 5
  • player B has seen questions 1 and 4
  • player C has seen questions 2 and 4

I though about removing the questions that top player has seen, but the position would change. Following the above example, player A has only got 2 questions left to play (2 and 4). However, if I remove 1, 3 and 5, the situation would be:

  • player A can play questions 2 and 4
  • player B can play question 2
  • player C cannot play anything because 1,3,5 are removed and he has already seen 2 and 4.

The score for this solution is zero, i.e. the player with least amount of available questions has zero available questions to play.

In this case it would be better to remove 1, 3 and 4, giving:

  • player A can play question 2
  • player B can play questions 2 and 5
  • player C can play question 5

The score for this solution is one, because the two players with least amount of available questions to play have one available question.

If the data size was small, I would be able to brute-force the solution. However, I have hundreds of players and questions, so I'm looking for some algorithm to solve this.

algorithm combinatorics
Edit
Report

2 Answers

4

Let's suppose that you have a general efficient algorithm for this. Concentrate on the questions left, rather than the questions removed.

You could use such an algorithm to solve the problem - can you choose at most T questions such that every user has at least one question to answer? I think that this is http://en.wikipedia.org/wiki/Set_cover, and I think solving your problem in general allows you to solve set cover, so I think it is NP-complete.

There is at least a linear programming relaxation. Associate each question with a variable Qi in the range 0<= Qi <= 1. Choosing questions Qi such that each user has at least X questions available amounts to the constraint SUM Uij Qj >= X, which is linear in Qj and X, so you can maximise for the objective function X with the linear variables X and Qj. Unfortunately, the result need not give you integer Qj - consider for example the case when all possible pairs of questions are associated with some user and you want each user to be able to answer at least 1 question, using at most half of the questions. The optimum solution is Qi = 1/2 for all i.

(But given a linear programming relaxation you could use it as the bound in http://en.wikipedia.org/wiki/Branch_and_bound).

Alternatively you could just write down the problem and throw it at an integer linear programming package, if you have one handy.

answered 2012-01-05T21:02:08.503
2

For completeness of the thread, here is a simple greedy, aproximating approach.

Place the solved questions in the previously discussed matrix form:

Q0    X
Q1  XX
Q2    X
Q3  X  
Q4   XX
    223

Sort by the number of questions solved:

Q0  X  
Q1   XX
Q2  X  
Q3    X
Q4  XX 
    322

Strike out a question with the most Xs among the players with most problems solved. (This is guaranteed to decrease our measure if anything is):

=======
Q1   XX
Q2  X  
Q3    X
Q4  XX 
    222

Sort again:

=======
Q1   XX
Q2  X  
Q3    X
Q4  XX 
    222

Strike again:

=======
=======
Q2  X  
Q3    X
Q4  XX 
    211

Sort again:

=======
=======
Q2  X  
Q3    X
Q4  XX 
    211

Strike again:

=======
=======
Q2  X  
Q3    X
=======
    101

It's O(n^2logn) without optimizations, so it is plenty fast for some hundreds of questions. It's also easy to implement.

It's not optimal as can be seen from this counter example with 2 strikes:

Q0 X     
Q1      X
Q2 XXX
Q3    XXX
Q4  XXXX
Q5 222222

Here the greedy approach is going to remove Q5 and Q2 (or Q3) instead of Q2 and Q3 which would be optimal for our measure.

answered 2012-01-13T23:22:03.557

Your Answer