snippetMinor
Matching Algorithm - How to maximize matched quantity with unique matching rules?
Viewed 0 times
uniquematchedwithquantityalgorithmmaximizehowrulesmatching
Problem
Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules:
$$\begin{aligned}
A\leftrightarrow B\\
C\leftrightarrow D\\
B+C\leftrightarrow F\\
D+A\leftrightarrow E\\
G+H\leftrightarrow B\\
\end{aligned}$$
The input to the matching algorithm is an array of variable size consisting of elements in $S$. Each item in the array has a particular size or "quantity" that can be matched (I imagine this can simply be modeled as edge weights).
For notational clarity -
$A \leftrightarrow B$ indicates "If an item exists in the input array of type A, it may match with an item of type B". The reverse is also true, so if there is $B$ it may match with $A$.
$B+C\leftrightarrow F$ indicates "If an item exists in the input array of type $B$, and another of type $C$, they may together match with an item of type $F$", the reverse is also true, so if there is $F$ and $C$, they may together match with $B$. $F$ by itself may not match with either $B$ or $C$.
The first question is, how to maximize the total quantity matched?
Second question is, how to optimize time complexity? If the algorithm is NP, please provide some proof or reason as to why it cannot be solved in P.
Intuitively, I think the problem could be modeled as a weighted bipartite graph and solved with a max-flow algorithm or dynamic programing. Once I construct the bipartite graph, the problem becomes easy to solve as bipartite graphs have been heavily studied.
The challenge is I'm not sure how to algorithmically construct the graph in a provably correct way given the rules or if it implies a different approach should be used. I'm thinking it may help to sort the input array by quantity and then not connect an edge if a vertex is marked as 'matched', but that alone doesn't solve the problem (i.e. BFS/DFS do not seem so help). Other potential avenues may be more generally 2D dynamic programing or set covers (although set covers are also in NP).
An Example with the (not quite bip
$$\begin{aligned}
A\leftrightarrow B\\
C\leftrightarrow D\\
B+C\leftrightarrow F\\
D+A\leftrightarrow E\\
G+H\leftrightarrow B\\
\end{aligned}$$
The input to the matching algorithm is an array of variable size consisting of elements in $S$. Each item in the array has a particular size or "quantity" that can be matched (I imagine this can simply be modeled as edge weights).
For notational clarity -
$A \leftrightarrow B$ indicates "If an item exists in the input array of type A, it may match with an item of type B". The reverse is also true, so if there is $B$ it may match with $A$.
$B+C\leftrightarrow F$ indicates "If an item exists in the input array of type $B$, and another of type $C$, they may together match with an item of type $F$", the reverse is also true, so if there is $F$ and $C$, they may together match with $B$. $F$ by itself may not match with either $B$ or $C$.
The first question is, how to maximize the total quantity matched?
Second question is, how to optimize time complexity? If the algorithm is NP, please provide some proof or reason as to why it cannot be solved in P.
Intuitively, I think the problem could be modeled as a weighted bipartite graph and solved with a max-flow algorithm or dynamic programing. Once I construct the bipartite graph, the problem becomes easy to solve as bipartite graphs have been heavily studied.
The challenge is I'm not sure how to algorithmically construct the graph in a provably correct way given the rules or if it implies a different approach should be used. I'm thinking it may help to sort the input array by quantity and then not connect an edge if a vertex is marked as 'matched', but that alone doesn't solve the problem (i.e. BFS/DFS do not seem so help). Other potential avenues may be more generally 2D dynamic programing or set covers (although set covers are also in NP).
An Example with the (not quite bip
Solution
The problem you are describing is a special case of the (weighted) 3-dimensional matching problem.1
Unlike regular 2-dimensional matching, maximum cardinality 3-dimensional matching is NP-hard, which means that weighted 3-dimensional matching is NP-hard. Therefore, solving this problem exactly in polynomial time doesn't seem feasible, unless the specific case you have here is easier than the general problem.
This special case seems easier than the general problem. My idea is to represent it as a minor modification to the regular 2d maximum weight matching problem. Note that for each of your combinations of 3 items, there is at least one item type that is not present in another combination (e.g. $E$ is only present in the combination $(A,D,E)$), I will call such an item type conflict-free. First, select a conflict free type for each combination of $3$ types: Here, I pick $E$ for $(A,D,R)$, $F$ for $(B,C,F)$, and $H$ treat items of such type differently than the others.
More concretely, for any combination of items $x,y,z$ of type $X,Y,Z$, where $Z$ is the chosen conflict-free type, we add only the edge $(x,y)$ of weight $f(q(x), q(y),q(z))$, where $q(i)$ denotes the quantity of item $i$ and $f$ is a function that determines the value of a matching based on the weight (including the type is of course also possible). Combinations with only $2$ types can be modeled as usual. Solving the maximum weight matching problem on this graph (which in your case is bipartite) provides the maximum sum of values that can be made.
For example, on the input $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, the graph will look like the following:
Red edges and their weights indicate the maximum matching. Note that the item of type E is not part of the graph, but only influences the weight of the two edges between types A and D. So the approach works for this case.
However, if we have items of type E with different quantity, we the weights of the edges will depend on which edges are selected. To see this, take the input $[A:5,\ A:4,\ D:6,\ D:4,\ B:3,\ E:5,\ E:1]$. We now get the following graph:
The edges between type $A$ and $D$ now no longer have a simple value as their weight, but a list of values. This is because each edge has to use one of the two $E$'s, but the same one cannot be reused. This means in particular that the blue matching has a value of $12+3=15$ instead of $12+12=14$, because the item $E$ of quantity $5$ can only be used once. Therefore, it is the red matching of value $21$ that is optimal.
I do not know whether the standard algorithms for weighted bipartite matching can deal with this modification on the weights or whether there we can make a modification to the standard algorithm to handle this.
1: Possible matches of the form $X+Y\leftrightarrow Z$ for items $x, y, z$ can be represented by the 3d-edge $(x,y,z)$ of weight the minimum of the quantities of the items $x,y,z$. Matches of the form $X\leftrightarrow Y$ for items $x,y$ can be represented by the 3d-edge $(x,y,d)$ of weight minimum of the quantities of items $x,y$ and a dummy vertex $d$ that is in no other 3d-edge.
Unlike regular 2-dimensional matching, maximum cardinality 3-dimensional matching is NP-hard, which means that weighted 3-dimensional matching is NP-hard. Therefore, solving this problem exactly in polynomial time doesn't seem feasible, unless the specific case you have here is easier than the general problem.
This special case seems easier than the general problem. My idea is to represent it as a minor modification to the regular 2d maximum weight matching problem. Note that for each of your combinations of 3 items, there is at least one item type that is not present in another combination (e.g. $E$ is only present in the combination $(A,D,E)$), I will call such an item type conflict-free. First, select a conflict free type for each combination of $3$ types: Here, I pick $E$ for $(A,D,R)$, $F$ for $(B,C,F)$, and $H$ treat items of such type differently than the others.
More concretely, for any combination of items $x,y,z$ of type $X,Y,Z$, where $Z$ is the chosen conflict-free type, we add only the edge $(x,y)$ of weight $f(q(x), q(y),q(z))$, where $q(i)$ denotes the quantity of item $i$ and $f$ is a function that determines the value of a matching based on the weight (including the type is of course also possible). Combinations with only $2$ types can be modeled as usual. Solving the maximum weight matching problem on this graph (which in your case is bipartite) provides the maximum sum of values that can be made.
For example, on the input $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, the graph will look like the following:
Red edges and their weights indicate the maximum matching. Note that the item of type E is not part of the graph, but only influences the weight of the two edges between types A and D. So the approach works for this case.
However, if we have items of type E with different quantity, we the weights of the edges will depend on which edges are selected. To see this, take the input $[A:5,\ A:4,\ D:6,\ D:4,\ B:3,\ E:5,\ E:1]$. We now get the following graph:
The edges between type $A$ and $D$ now no longer have a simple value as their weight, but a list of values. This is because each edge has to use one of the two $E$'s, but the same one cannot be reused. This means in particular that the blue matching has a value of $12+3=15$ instead of $12+12=14$, because the item $E$ of quantity $5$ can only be used once. Therefore, it is the red matching of value $21$ that is optimal.
I do not know whether the standard algorithms for weighted bipartite matching can deal with this modification on the weights or whether there we can make a modification to the standard algorithm to handle this.
1: Possible matches of the form $X+Y\leftrightarrow Z$ for items $x, y, z$ can be represented by the 3d-edge $(x,y,z)$ of weight the minimum of the quantities of the items $x,y,z$. Matches of the form $X\leftrightarrow Y$ for items $x,y$ can be represented by the 3d-edge $(x,y,d)$ of weight minimum of the quantities of items $x,y$ and a dummy vertex $d$ that is in no other 3d-edge.
Context
StackExchange Computer Science Q#110652, answer score: 2
Revisions (0)
No revisions yet.