Greedy Algorithm Implementation

Question

You know who knows who among n people that you would like to have come to a party. Assume "knows" is symmetric: If I know you, you know me. You make further requirements that you want each person to have at least 5 new people to meet at the party, and also, so nobody feels too isolated, each person should already know at least 5 people at the party. Your original list may not satisfy these extra two conditions, so you may need to eliminate some people from the invitation list (or maybe you cannot have a party at all with these restrictions). Find a largest possible subset of the n people that you could invite and satisfy the the other two requirements. For the basic problem, find an O(n^3) algorithm and explain its order and its logic.

I ask not for the answer, but for guidance on where to start.

Iila

The first step is always to draw (or generate) a couple of graphs (say 10-20 vertices) and try to find the solution manually. That gives you a rough idea of what the task is and where the difficulties lie. – Ethiopia

what are the inputs to be given to the algorithm ? – Sogdian

Answer 1

Sounds like a good place to apply a graph algorithm.

Form a graph of people, G. For n people there will be n nodes in the graph. Link nodes i and j if person i knows person j.

Let the first iteration of G be called G_0. Obtain G_1 by making a pass through G and eliminate any person who knows too many or too few people. (That is, eliminate person i if the number of links to i is < 5 or > n-5.)

Repeat the process, obtaining G_2, G_3 up to a maximum of n (or so) iterations, obtaining G_n. The people remaining in this graph are the people you should invite.

Each of the n passes requires a check of n people against n other people, so the algorithm is O(n^3).

---

MATLAB code to accomplish this (you didn't ask for it, but I thought it was interesting and wrote it anyway):

% number of people on original list
N = 10

% number of connections to (attempt) to generate
% may include self-links (i,i) or duplicates
M = 40

% threshold for "too few" friends
p = 3

% threshold for "too many" friends
q = 3

% Generate connections at random
G = zeros(N);
for k = 1:M
    i = randi(N);
    j = randi(N);
    G(i,j) = 1;
    G(j,i) = 1;
end

% define people to not be their own friends
for i = 1:N
    G(i,i) = 0;
end

% make a copy for future comparison to final G
G_orig = G

% '1' means invited, '0' means not invited
invited = ones(1,N);

% make N passes over graph
for k = 1:N
    % number of people still on the candidate list
    n = sum(invited); 
    % inspect the i'th person
    for i = 1:N 
        people_known = sum(G(i,:));
        if invited(i) == 1 && ((people_known < p) || (people_known > n-q))
            fprintf('Person %i was eliminated. (He knew %i of the %i invitees.)\n',i,people_known,n);
            invited(i) = 0;
            G(i,:) = zeros(1,N);
            G(:,i) = zeros(1,N);
        end
    end
end

fprintf('\n\nFinal connection graph')
G

disp 'People to invite:'
invited

disp 'Total invitees:'
n

Sample output (10 people, 40 connections, must know at least 3 people, must not know at least 3 people)

G_orig =

     0     0     1     1     0     0     0     0     1     0
     0     0     0     0     0     1     0     0     0     1
     1     0     0     1     1     1     0     0     0     1
     1     0     1     0     0     1     0     1     1     0
     0     0     1     0     0     0     1     0     1     1
     0     1     1     1     0     0     0     1     0     1
     0     0     0     0     1     0     0     0     1     0
     0     0     0     1     0     1     0     0     0     1
     1     0     0     1     1     0     1     0     0     1
     0     1     1     0     1     1     0     1     1     0

Person 2 was eliminated. (He knew 2 of the 10 invitees.)
Person 7 was eliminated. (He knew 2 of the 10 invitees.)


Final connection graph
G =

     0     0     1     1     0     0     0     0     1     0
     0     0     0     0     0     0     0     0     0     0
     1     0     0     1     1     1     0     0     0     1
     1     0     1     0     0     1     0     1     1     0
     0     0     1     0     0     0     0     0     1     1
     0     0     1     1     0     0     0     1     0     1
     0     0     0     0     0     0     0     0     0     0
     0     0     0     1     0     1     0     0     0     1
     1     0     0     1     1     0     0     0     0     1
     0     0     1     0     1     1     0     1     1     0

People to invite:

invited =

     1     0     1     1     1     1     0     1     1     1

Total invitees:

n =

     8

Baldachin

Interestingly, I started writing this in Python but switched to MATLAB. It was much easier to write in MATLAB. – Baldachin

very nice, clear explanation. A small improvement might be to eliminate all of each type of person on alternate passes. First pass might eliminate people who know too few others, but it could just as easily be the 'over-friendly'; neither can come anyway, and their elimination can cause some others to change status. IMHO, it isn't necessary for the algorithm in general, but might make it easier to see Big-O. Just a small thought. – Ballade

@gbulmer: Thank you for the compliment (I pride myself on readable code.) As regards your suggestion: I contemplated it but decided it would require tracking additional state, so I favoured the simplest possible solution. You will also note I've not optimised at all - in this example the solution was complete after the first pass. I could have detected that and stopped, but again - extra logic. ;) – Baldachin

Answer 2

I am assuming following data structure for the representation of the information:

Person
    name : string, if this is empty or null, the person isnt not invited to party
    knows: array of pointers to type Person. Indicates whom this person 'knows'
    knows_cnt : size of "knows" array

Details of everyone (including host) can be stored in "Person individuals[n]".

The host of party being at first position.

A subroutine that i might need for algo:

RemovePerson (individuals, n, i)
// removes i'th person from individuals an array of n persons

    set individuals[i].name to empty so that this person is discarded

    For j from 1 to individuals[i].knows_cnt
    // as knows is symmetric, we can get the persons' contact right away
        Person contact = individuals[i].knows[j]

        if contact.name is empty, 
            continue

        modify contact.knows to remove i'th person. 
        modify corresponding contact.knows_cnt
    end for

end RemovePerson

The proposed algorithm:

change = true 
invitees = n

while [change == true]
    change = false

    for i = 2 to n do
    // start from 2 to prevent the host getting discarded due to condition #2

        if individuals[i].name is empty, 
            continue

        // condition #1,
        // check if the person knows atleast 5 people
        if individuals[i].knows_cnt < 5
            change = true 
            invitees = invitees  - 1
            RemovePerson(individuals, n, i)

        // condition #2
        // check to find out if the person will get to know 5 new people
        if (invitees - individuals[i].knows_cnt) < 5
            change = true 
            invitees = invitees  - 1
            RemovePerson(individuals, n, i)

    end for

end while   

return invitees

Let me know if you face any difficulty in understanding this algo.

Sogdian

Whoever downvoted this: I'm curious to know why. This algorithm is essentially correct (even if it's a bit long-winded due to Java.) – Baldachin