0
$\begingroup$

I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this:

User (U) | Group (G) | Price (P)
================================
U1       | G1        | P11
U2       | G1        | P12
--------------------------------
U1       | G2        | P21
U2       | G2        | P22
--------------------------------
U3       | G3        | P33
U4       | G3        | P34
--------------------------------
U5       | G4        | P45

A user (U) can apply to be an admin of more than one Groups (G). There is a salary (P) that must be given to U if U is selected as the admin of G (U can demand any arbitrary number as salary for a group G).

The goal is to satisfy these conditions

  • Every group should have exactly 1 admin.
  • A User should not be the admin of more than 1 group.
  • Find admins for as many groups as possible.
  • The sum of salaries should be minimum.

Examples/Notes

  • If there are only two applications and are by the same user U (say for groups G1 and G2, expected salaries P1 and P2), only either of G1 and G2 will get an admin. If P1 > P2, U should be adjudged the admin of G1 (and not G2).

I'm not very sure which category of Assignment problem does this fall into. My approach was greedy and doesn't look optimal.

  • Group-wise sort (ascending) the expected salary.
  • Arbitrarily allocate a user to a group where there is only 1 admin-ship request. Remove this user from other group-admin requests.
  • Among the first request across groups, find the maximum and allocate the user to the group. Remove this user from other group admin-ship requests.
  • Repeat

Question: What is an optimal solution to this problem?

$\endgroup$
  • $\begingroup$ Maybe I misunderstand your first condition, but why do you demand that each group should be associated with only one user? It's not a group if there's just one member. I'll post a preliminary answer to the question as it's posed right now. $\endgroup$ – Lieuwe Vinkhuijzen May 4 '16 at 13:50
  • $\begingroup$ On second thought, I don't understand your first condition. You say that each group should have just one member, and you also say that each user should have one group, in other words, you want a maximum matching (link) in a weighed bipartite graph. Blossim's algorithm solves that problem. Is this what you meant? $\endgroup$ – Lieuwe Vinkhuijzen May 4 '16 at 13:59
  • $\begingroup$ @LieuweVinkhuijzen I've translated the question to a more practical scenario (Every group is looking for an admin and an admin expects a certain salary). I'll look into maximum matching (link) next. Thank you. $\endgroup$ – TJ- May 4 '16 at 14:30
  • $\begingroup$ I don't understand your condition. I think trying to deal with the case where you can't satisfy the first condition leads you a vaguely-stated, ill-specified question. I suggest that you rephrase your question to list a set of requirements (every group has exactly 1 admin; the sum of salaries is minimum); except that if there's no assignment where every group has exactly 1 admin then something (you fill in the something; I can't quite figure out what the requirements are in that case -- I don't know what you mean by "those groups should be behind..." -- can you rephrase more carefully?). $\endgroup$ – D.W. May 5 '16 at 0:34
  • $\begingroup$ Can you have an assignment where one admin is assigned to more than one group? It sounds like not, but you should state that explicitly. $\endgroup$ – D.W. May 5 '16 at 0:35
3
$\begingroup$

You are probably looking for a solution to the following optimization problem.

Weighted maximum biparite matching. Given a weighted bipartite graph $G=(U\cup V, E)$ with weights $w\colon U\times V \rightarrow \mathbb{N}$, find a set of edges $A\subseteq U\times V$ such that all edges in $A$ are disjoint (that is, no two edges are adjacent, that is, no group has two admins and no admin has two groups) and the sum $\sum_{a\in A}w(a)$ is minimized, and it is not possible to add another pair $(u,v)\in U\times V$ to $A$ without violating the non-adjacency constraint.

The sets $U$ and $V$ are the users and the groups, respectively. The set of edges $E$ is the set of applications (user-group pairs) and the set of weights is the salary of a given assignment. The Blossom algorithm (link) is a optimization algorithm that finds a maximum matching, and it can be adapted to solve the weighted case.

A final note: you seem to be optimizing two objectives at once: both the minimum salary, and the maximum number of covered groups. Obviously these objectives conflict: covering less groups gives a lower salary. Fortunately, the Bloom algorithm will find a maximum matching, so it will cover as many groups as is possible, and within the set of matchings that cover the maximum number of groups, it finds the one with the lowest sum salary.

$\endgroup$
1
$\begingroup$

Checking whether there's a valid assignment

You can check in polynomial time whether or not there exists any assignment such that every admin is assigned to only one group, and every group has exactly one admin. Simply using maximum matching algorithms.

Finding the assignment of least cost, if one exists

If the answer to the above query was "yes, at least one such assignment exists", you can find the assignment of lowest cost using weighted maximum matching: you assign a weight to each edge that is equal to the negative of the salary, and then look for a maximum-weight matching algorithm.

In other words, this is exactly an instance of the assignment problem. There are standard polynomial-time algorithms for the assignment problem, so this problem can be solved, too.

Handling the case where no such assignment exists

What if there doesn't exist any assignment where every admin is assigned to exactly one group and every group has exactly one admin? Well, it's not clear from the question what you want to happen in this case, so it's hard to suggest a specific algorithm. Your first step is to identify (1) a set of hard requirements that absolutely must be met in this situation, no matter what, and (2) an objective function that you want to maximize. Once you've identified those, then one can look for an algorithm that solves the associated optimization problem. But until you can articulate that, the problem is not well-defined. The core problem is that you can't simultaneously optimize for two quantities at once (maximize number of groups covered, minimize total salary), because in general there will be a tradeoff between the two, and you need how you want to trade off between them before you can ask for an algorithm to find the optimal tradeoff.

In this case there is a technique you can use to enumerate all Pareto-optimal tradeoff points:

  1. First, check for the optimal assignment that covers all groups (if one exists), using the techniques above.

  2. Next, check for the lowest-cost assignment that covers $n-1$ of the $n$ groups (i.e., where all but one of the groups has an admin). You can do this by adding a fake admin whose salary is \$0 and who can administer any group, then solving the assignment problem. Any solution to this modified problem that covers all $n$ groups will correspond to a solution to the original problem that covers $n-1$ groups, at the lowest possible cost.

  3. Next, check for the lowest-cost assignment that covers $n-2$ of the $n$ groups, by adding two fake admins. Repeat: for each $k$, find the lowest-cost assignment that covers $k$ of the groups.

This gives you $n$ candidate solutions with different tradeoffs between "number of groups covered" and "lowest total salary". You can then decide which of those you want as your final solution, depending on how you want to trade off those two quantities.

Greedy algorithm

No, the greedy algorithm does not provide an optimal solution, in general. It's not hard to construct counterexamples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.