An Algorithm for Multi-Attribute Diverse Matching

1 Introduction

The bipartite matching problem occurs in many applications such as healthcare, advertising, and general resource allocation. Weighted bipartite b-matching is a generalization of this problem where each node on one side of the market can be matched to many items from the other side, and where edges may also have associated real-valued weights. Examples of weighted bipartite b-matching include assigning children to schools [Drummond et al., 2015; Kurata et al., 2017], reviewers to manuscripts [Charlin and Zemel, 2013; Liu et al., 2014], and donor organs to patients [Dickerson and Sandholm, 2015; Bertsimas et al., 2019].

Ahmed et al. [2017] introduced the notion of diverse bipartite b-matching, where the goal was to simultaneously maximize the "efficiency" of an assignment along with its "diversity." For example, a firm might want to hire several highly-skilled workers, but if that firm also cares about diversity it may want to ensure that some of those hires occur across marginalized categories of employees. They proposed an objective which combined economic efficiency and diversity demonstrating that, in practice, reducing the efficiency of a matching by small amounts can often lead to significant gains in diversity across a matching. However, their formulation was limited to diversity for a single feature. It also relied on solving a general Mixed-Integer Quadratic Program (MIQP), which is flexible but computationally intractable.

In this work, we generalize the diverse matching problem and introduce matchings where each worker has multiple features (e.g., country of origin, gender) and our goal is to form diverse teams with respect to all these features. We found that the problem with a single feature, studied by Ahmed et al. [2017], can be reduced to a minimum quadratic cost maximum flow formulation and solved in polynomial time by an existing algorithm [Minoux, 1986]. In contrast, we provide NP-hardness results for the general case of multiple features.

Our contributions. The paper's main contributions follow:

• We provide the first pseudo-polynomial time algorithm for the diverse bipartite b-matching w.r.t. multiple features problem with class-specific weights. 1 The key insight lies in detecting negative cycles in an auxiliary graph repre-

1 That is, under conditions when the cost of assigning all items from one feature set to an item on the other side of the graph is the same. This holds when, e.g., one is matching academic papers to reviewers where each reviewer can specify exactly one field of expertise and the cost of assigning a paper to any of the reviewers within the same field is the same but differs across fields.

sentation, which we use to either provide incremental improvements to the incumbent diverse matching or prove that our negative-cycle-detection algorithms have found a globally-optimal matching. We also provide a general MIQP formulation for this problem.

• We then extend the algorithm to the diverse bipartite bmatching problems with general edge weights, where edge weights of nodes within a category can be different.
• Lastly, we demonstrate our algorithm's applicability to paper-reviewer matching. Our algorithm takes less time to converge to an optimal solution than the proposed MIQP approach (using a state-of-the-art commercial solver).

2 RelatedWork

Matching people to form diverse teams leverages the intersection of two past areas of research: the role of team diversity in collaborative work and how diversity among groups of resources is measured and used to form/match teams. Compared to related work, this paper provides a practical, highperforming method to perform diverse b-matching that can enable applications like diverse team formation or diverse resource allocation. Below we will use the example of diverse team formation (for example, in project teams within a company) to provide a concrete example to place prior work in context; however, our proposed approach is generally applicable to any diverse matching problem.

In the example of forming teams, the traditional approach is to use weighted bipartite b-matching (WBM) methods [Basu Roy et al., 2015]. These methods maximize the total weight of the matching while satisfying some constraints. However, there are two major issues with these approaches. First, it assumes that the value provided by a person in a team is always fixed and independent of who else is in the team. This assumption may not hold in many cases. A new team member may provide more added value to the team if she is added to a smaller team compared to the case if she is added to a larger team. This property of diminishing marginal utility can be mathematically captured by a family of functions called submodular functions, which we define later. Second, existing approaches do not account for diversity within a team, where teams with workers from different backgrounds may be desirable. For example, different types of worker diversity have a direct impact on the success rate of tasks [Ross et al., 2010]. Likewise, firms with a higher number of employees with higher education and diversity in the types of educations have a higher likelihood of innovating [Østergaard et al., 2011] and increasing revenue for firms [Hunt et al., 2015]. In this paper, we address both these issues.

Past researchers have generally measured diversity by defining some notion of coverage-that is, a diverse set is one that covers the space of available variation. Mathematically, researchers have done so via the use of submodular functions, which encode the notion of diminishing returns [Lin and Bilmes, 2012]; that is, as one adds items to a set that are similar to previous items, one gains less utility if the existing items in the set already "cover" the characteristics added by that new item. For example, many previous diversity metrics used in the information retrieval or search communities-including Maximum Marginal Relevance (MMR) [Carbonell and Goldstein, 1998] and Determinantal Point Processes [Kulesza et al., 2012]-are instances of submodular functions. These functions can model notions of coverage, representation, and diversity [Ahmed and Fuge, 2018] and they have been shown to achieve top results on common automatic document summarization benchmarks-e.g., at the Document Understanding Conference [Lin and Bilmes, 2012].

Within matching, our work is closest to that of Ahmed et al. [2017], which used a supermodular function to propose a diverse matching optimization method. Other researchers have also approached similar problems, with diversity either as an objective or as a constraint. For instance, G¨olz and Procaccia [2019] match migrants to localities in a way that maximizes the expected number of migrants who find employment. Benabbou et al. [2018] study the trade-off between diversity and social welfare for the Singapore housing allocation. They model the problem as an extension of the classic assignment problem, with additional diversity constraints. Lian et al. [2018] solve the assignment problem when preferences from one side over the other side are given and both sides have capacity constraints. They use order weighted averages to propose a polynomial-time algorithm which leads to high quality and more fair assignments. Agrawal et al. [2018] show that a simple iterative proportional allocation algorithm can be tuned to produce maximum matching with high entropy. Finally, Kobren et al. [2019] proposed two fairness-promoting algorithms for the paper-reviewer matching problem. They demonstrate that their algorithm achieves higher utility compared to state of the art matching algorithms that optimize for fairness only. In contrast, our goal is to develop an algorithm for finding the optimal assignment which maximizes utility as well as diversity along multiple features as an objective-along with having constraints on workload.

We define a utility function that can be tuned to balance the diversity and total weight of matching. The diversity function is inspired by the Herfindahl index [Hirschman, 1964], which is a statistical measure of concentration and commonly used in economics. We provide a new algorithm that models the problem using an auxiliary graph and uses a heuristic improvement of the negative cycle detection of Bellman-Ford by Goldberg and Radzik [1993] 2 to find negative cycles and cancel them on a new graph to obtain an optimal solution for the original problem.

3 Preliminaries

In this section, we first define the preliminaries for a diverse matching problem, where workers are to be matched to teams and each team wants workers belonging to a diverse set of features. In our problem, we are given a set of features for the workers. Let F = {f1, · · · , f|F|} denote the feature set for the workers. An example of a feature set could be {country of citizenship, gender}. Each feature fk ∈ F has one of the values Fk = {fk,1, · · · , fk,|Fk|}. Let |Fk,k′ | denote the number of workers having value fk,k′ for feature fk. The set of workers is denoted by X = {x1, . . . , xn}. X is partitioned into |V| subsets V1, · · · , V|V|, where each subset Vj corresponds to a feature set vj = {vj,1, · · · , vj,|F|}, where ∀1 ≤ k ≤ |F|, vj,k ∈ Fk.

2 We used the negative cycle detection algorithm by Goldberg and Radzik [1993]. Cherkassky et al. [1993] compared the performance of multiple negative cycle detection algorithms, and the algorithm by Goldberg and Radzik [1993] was one of the fastest.

We wish to form a set of teams {T1, . . . , Tt} of the workers where each team Ti has a demand of di, specifying the number of workers that need to be assigned to it. Each worker can be assigned to at most one team.

The diversity loss of an assignment is denoted by D and is equal to ∑|F| k=1 λkDk, where Dk shows the diversity loss w.r.t. feature fk, and λk ∈ Z ≥0 is a constant. Let ci,k,k′ denote the number of workers in Ti having value fk,k′ ∈ Fk for feature fk. Then, Dk = ∑ti=1 ∑|Fk| k′=1 c2i,k,k′ . The cost of assigning each worker having value fk,k′ ∈ Fk for feature fk to team Ti is denoted by ui,k,k′ ∈ Z ≥0 . We assume all costs are integers. The total cost of an assignment is TU = ∑|F| k=1 TUk where TUk = ∑ti=1 ∑|Fk| k′=1 ci,k,k′ · ui,k,k′ .

Our goal is to minimize the objective function which is equal to D + λ0TU, where λ0 ∈ Z ≥0 . To understand why minimizing Dk makes an assignment more diverse w.r.t fk, consider Figure 1. In the left assignment, D2 = 8, and in the right assignment D2 = 4, and the right assignment is more diverse w.r.t f2, i.e. gender. By setting λ parameters, we assume that the relative importance between factors is not qualitative and can be quantified. Next, we provide Theorem 1, which shows that this problem is NP-hard.

Theorem 1. Minimizing the supermodular diversity loss function w.r.t multiple features is NP-hard.

Proof. We show a reduction from a variation of 3-COLOR problem which is as follows: given a graph G = (V, E) with n vertices, is there a coloring with n1 vertices of color c1, n2 vertices of color c2, and n3 vertices of color c3, such that no two adjacent vertices receive the same color, and all the vertices are colored? It could be shown this variation is NPhard by a reduction from classic 3-COLOR problem.

The reduction from 3-COLOR to multiple-attribute diverse matching is as following: In 3-COLOR, assign a feature fk to each edge ek = (vk1 , vk2 ) ∈ E, and a worker to each vertex. Let fk,i denote the value of fk for the worker corresponding to vi ∈ V . Let fk,i = i if i ̸= k1, k2. Otherwise, let fk,i = 0. The goal is to form three teams T1, T2, T3 with demands d1 = n1, d2 = n2, d3 = n3, respectively. We assume that all the costs of assigning workers to the teams are zero, therefore the objective function is to minimize the total diversity loss. Consider an arbitrary edge ek = (vk1 , vk2 ). If the endpoints of ek belong to different teams, fk contributes n1 + n2 + n3 to the objective function since all the workers inside a team have different values for fk. Otherwise, it contributes n1 + n2 +n3 -2+22 since workers corresponding to vk1 , vk2 are the only workers having the same value for fk inside a team. If the cost of the optimal solution for the diverse matching problem is (n1 +n2 +n3) · |E|, there does not exist a pair of workers in a team where the vertices corresponding to them are neighbouring in G. Otherwise if the cost of the optimal

We are interested in solving this NP-hard problem. We begin by presenting two different representations of instances of the problem: one in matrix form (used for expositional ease), and the other in graph form (used to build our optimal diverse matching algorithm in Section 4).

Matrix Representation. An example of matrix representation with three teams and two countries and two genders is shown in Table 1. Each column corresponds to a feature set and each row corresponds to a team. Entry wi,j shows the number of workers with feature set vj assigned to Ti. We introduce a dummy team T0, and w0,j shows the number of workers with feature set vj who are not assigned to any team.

Matching Representation. In this representation, a bipartite graph G = (X ∪ T ,E) is given. The nodes in X correspond to the workers, and are partitioned into |V| subsets where each subset corresponds to a feature set. Each vertex in T corresponds to a team in {T0, T1, T2, · · · , Tt}. The assignment of workers to teams forms a b-matching, where the degree of each node Ti for 1 ≤ i ≤ t is di. All workers who are not assigned to any team T1, · · · , Tt get assigned to the dummy team T0. Degree of each node x ∈ X is exactly one.

Local Exchange. A local exchange happens when a group of teams decides to transfer one or more workers between each other while maintaining the total number of workers in each of them. The exchange is done in a way that the initial demands of all the teams are fulfilled. Arrows in Table 1 show a local exchange in a matrix representation.

In this exchange, one worker from V2 is moved from T3 to T1. Two workers from V1 are moved. One is moved from T1 to T2, and the other one is moved from T2 to T3. The set of edges of local exchange in a matrix representation is called a cycle. The source-transitions of a cycle are the cells without any input edges, and the sink-transitions are the cells without any output edges. In Table 1, the cells corresponding to w3,2 and w1,1 are source-transitions, and the cells corresponding to w1,2 and w3,1 are sink-transitions.

Figure 2 shows the same local exchange operation using a matching representation. In this figure, the black matching shows the initial assignment, and the dotted matching shows the assignment after the exchange operation is done.

Gain of a local exchange. Our goal is to minimize the objective function f, by doing some local exchanges. To find out, we first calculate the marginal gain from a given exchange operation which is the difference between the objective values before and after a local exchange. In order to simplify this concept, we use the following definition:

Embedding of Matrix Representation. Consider a given matrix representation M, it can be embedded into a matrix Mk for a fixed feature fk in the following way: all the columns in M corresponding to the same value fk,k′ of fk, are combined into a single column in Mk. For example, embedding of the matrix representation in Table 1 into M1,M2 w.r.t. the features country and gender are shown in Tables 2 and 3. Since in M1, the number of people assigned from each country to each team is not changed, ∆1 = ∆(λ0 · TU1 + λ1D1) = 0. According to M2, ∆2 = ∆(λ0 ·TU2+λ2D2) = λ0 ( -u3,2,2+u1,2,2-u1,2,1+ u3,2,1 )+λ2 ((c3,2,2-1)2-(c3,2,2)2+(c1,2,2+1)2-(c1,2,2)2+ (c1,2,1 - 1)2 - c21,2,1 + (c3,2,1 + 1)2 - c23,2,1 ).

It can be seen that the contribution of the cells which are not source-transition or sink-transition to the gain of a local exchange is zero (all the cells in the local exchange in Table 2, and the node corresponding to c2,2,1 in M2). If the net gain, i.e. ∆1 + ∆2, is negative, then the local exchange can be considered beneficial and we can transfer the workers.

4 Negative-Cycle-Detection-based Algorithms

In this section, we explain our algorithm for finding the optimum assignment. First, we build an auxiliary graph G′ . For each team Ti ∈ {T0, · · · , Tt}, there is a switch in G′ with |V| input ports, and |V| output ports. Each port is a node in G′ , and each switch is a directed bipartite graph, with edges going from its input ports (nodes) to its output ports. In Figure 3, each box is a switch. Inside a switch Ti, there is a directed edge from each input port to each output port. If the directed

edge is connecting two ports such that their corresponding

combinations of features do not have the same value for any

Algorithm 1: Find optimal diverse b-matching

Input : Directed weighted graph G′ , initial feasible b-matching Q which satisfies team demands. Output: Optimal diverse b-matching while ∃ a negative cycle C ∈ G′ do // Perform a local exchange operation along C; for e ∈ C do // Assume edge e is from output port Oi1 j of team Ti1 to input port I i2 j of another team Ti2 ; // Move one worker with feature set vj = {f1,k′1 , · · · , f|F|,k′ |F| } from team Ti1 to team Ti2 : ∀k ∈ {1, · · · , |F|}: ci1,k,k′k - = 1, ci2,k,k′k + = 1; Update weight of edges of G′ w.r.t to the new values of ci1,k,k′k , and ci2,k,k′k ;

features, the weight of this edge is equal to zero. Otherwise, per each feature fk that has the same value, -2λk is added to the weight of this edge.

The reason behind assigning these weights to the edges is to make sure in a local exchange, considering a fixed feature fk, the cells which are not a source-transition or a sinktransition w.r.t. Mk, have zero contribution to ∆(Dk).

For each pair of teams Ti1 and Ti2 where i1 ̸= i2, and for each feature combination vj, there is a directed edge from output port Oi1 j of switch Ti1 to the input port I i2 j of switch Ti2 , and weight of this edge captures the difference in the objective function when in the matrix representation a person in column Vj (with feature set vj) is moved from Ti1 to Ti,2.

Each cycle in this graph corresponds to a cycle in a matrix representation and local exchanges along them have the same gain. Figure 3 shows a cycle which is corresponding to the cycles in Table 1 and Figure 2.

After constructing the auxiliary graph, we run Algorithm 1. Algorithm 1 moves workers from one team to another if it detects a negative cycle.

Algorithm 1 takes as input an initial feasible solution Q as input. To find Q, we first find a feasible solution, which satisfies all the demand constraints. In order to find an initial feasible solution, in each iteration, consider the first subset of workers in the the bipartite graph G (Vj) with at least one unassigned worker, and the first team (Ti) such that the number of workers assigned to it is less than its demand (In the first iteration, we start with V1, T1, and all the workers are unassigned). Assign un-assigned workers from Vj to Ti, until either demand of Ti is fully satisfied, in this case, move to the next team (i = i+1), or all the workers from Vj are assigned, then let j = j +1. Repeat this procedure until all the demand constraints are satisfied. Time complexity of this procedure is O(|V| + t).

In Algorithm 1, any negative cycle detection algorithm can be used to detect negative cycles in G′ . We use a heuristic improvement of Bellman-Ford proposed by Goldberg and Radzik [Goldberg and Radzik, 1993] in our experiments.

5 Proof of Optimality

In this section, we prove that Algorithm 1 gives the optimum solution for diverse bipartite b-matching problem.

Assume after the algorithm ends, the final assignment is a local optimum P, and the optimum solution is P ∗ . Consider the matching representations of P and P ∗ . Since all the nodes in P and P ∗ are matched, the symmetric difference of P and P ∗ (P ⊕ P ∗ ) can be decomposed into a set of alternating even cycles. Each local exchange along an alternating cycle corresponds to a cycle in the matrix representation.

Before proving Thm. 2, we need the following definitions:

Maximal Cycle. A cycle y in a matrix representation M is maximal if its source-transitions and sink-transitions are source-transition and sink-transition w.r.t all the edges in M as well. For example, consider Table 4. Let's call the dotted cycle yg, the dashed cycle yr, and the solid-line cycle yb. yg has two source-transitions w1,1,w0,3, and it has two sink-transitions w0,1,w1,3. Since there are no edges going out of w1,3,w0,1, and no edges going into w0,3,w1,1, yg is a maximal cycle. Cycles yr, yb are maximal cycles as well. Therefore, {yg, yb, yr} gives a maximal cycle decomposition for M. However, if we consider embedding of M w.r.t gender (M2), then yr is not a maximal cycle anymore, and {yg, yr ∪ yb} gives a maximal cycle decomposition w.r.t M2 and M1(embedding w.r.t countries). A cycle is called allmaximal cycle if it is maximal w.r.t all the matrix representations M1, · · · ,M|F|. In this example, {yg, yr ∪ yb} gives an all-maximal cycle decomposition.

Lemma 1. The set of all the edges of P ⊕P ∗ can be decomposed into a set of all-maximal cycles. 3

Theorem 2. Algorithm 1 finds the global optimum for the diverse b-matching problem.

Proof. Let f(P) show the value of the objective function for the assignment P . f(P ∗ ) - f(P) < 0 therefore:

3 Due to space constraints, we omit this proof to the full version.

Where y′k (1 ≤ k ≤ ℓ′ ) is the kth cycle in the all-maximal cycle decomposition, and y′k,k is applying the local exchange of the cycle y′k at step k. The initial step is the assignment P. Since f(P ∗ ) - f(P) < 0, there must be a maximal cycle y′g such that gain(y′g,g ) < 0. We wish to show gain(y′g,1 ) < 0, which implies starting from the initial assignment P, a local exchange can be done with a negative gain, and P is not a local optimum which is a contradiction.

Let D(y′g,g ), U(y′g,g ) denote respectively the change in the diversity loss, and the change in the utility when applying a local exchange y′g in step g. Let Dfk (y′g,g ), Ufk (y′g,g ) denote the change in the diversity loss w.r.t the feature fk, when applying y′g,g . Therefore:

Lemma 2 shows if Dfk (y′g,g ) < 0, then Dfk (y′g,1 ) < 0. As a result, D(y′g,g ) < 0 implies D(y′g,1 ) < 0. It is easy to see that U(y′g,g ) = U(y′g,1 ). Therefore, gain(y′g,g ) < 0 implies gain(y′g,1 ) < 0, and the proof is complete.

Lemma 2. If Dfk (y′g,g ) < 0, then Dfk (y′g,1 ) < 0. 3

Theorem 3. The running time of the algorithm is O((λmax · |F| · n2 + λ0U) · |V|2 · t2 (|V| + t)), where U is the maximum cost of an initial feasible b-matching and λmax = max{λ1, · · · , λ|F|}.

In order to prove this theorem, first we show the following lemmas hold.

Lemma 3. The number of iterations of our algorithm is at most λmax · |F| · n2 +λ0U. 3

Lemma 4. The complexity of each iteration of the algorithm is O(|V|2 · t2 (|V| + t)). 3

Combining Lemma 3 with Lemma 4, and considering O(|V| + t) time complexity for finding an initial feasible solution, yields Theorem 3.

6 DiverseWeighted Bipartite b-Matching

In this section, we extend our algorithm to solve the case where the cost of assigning workers from the same feature set to a team can be different. First, in each switch we put input and output ports for each worker. Inside each switch, there is a complete bipartite graph from input ports to the output ports. Consider an edge between an input port to an output port corresponding to workers xi and xj . Per each feature fk where xi, xj have the same values for fk, -2λk is added to the weight of the edge between xi, xj .

Consider an edge from output port xi1 k of switch Ti1 to input port xi2 k of switch Ti2 , where xk ∈ Vj . The weight of this edge is equal to the change in the objective function by moving one worker from Vj out of Ti1 , and adding that worker to Ti2 . The proof of the following theorem is similar to Thm. 3.

Theorem 4. The running time of the algorithm for general weights is O((λmax · |F| · n2 +λ0U) · n2 · t2 (n+ t)), where U is the maximum cost of any feasible b-matching.

7 Experimental Validation &Discussion

To demonstrate the effectiveness of the proposed method, we apply it to a dataset of reviewer paper matching. First, we find the optimal solution for multi-feature reviewer paper matching and compare it to the single feature diverse matching method. We also provide the MIQP formulation of the same problem based on literature and show how our algorithm is faster to the Gurobi based MIQP solver.

For the reviewer assignment problem, where each reviewer has multiple features, we want to match each paper with reviewers who are not only from different expertise areas (clusters), but also belong to different genders. We use the multiaspect review assignment evaluation dataset [Karimzadehgan and Zhai, 2009], a benchmark dataset from UIUC. It contains 73 papers accepted by SIGIR 2007, and 189 prospective reviewers who had published in the main information retrieval conferences. The dataset provides 25 major topics and for each paper in the set, an expert provided 25-dimensional label on that paper based on a set of defined topics. Similarly for the 189 reviewers, a 25-dimensional expertise representation is provided.

To compare our method (Algorithm 1) with a baseline, we formulate a multi-feature MIQP variant of our problem, which is an extension of the single-feature formulation provided in [Ahmed et al., 2017] and is given by:

To set up the graph for our method, we first cluster the reviewers into 5 clusters based on their topic vectors using spectral clustering. To calculate the relevance of each cluster for any paper, we take the average cosine similarity of label vectors of reviewers in that cluster and the paper. We set the constraints such that each paper matches with exactly 4 reviewers, and no reviewer is allocated more than 1 paper. To increase dataset size, we double the number of reviewers by creating a copy of each reviewer. As the original dataset lacks gender information, we added a new feature to each reviewer in this dataset by randomly adding one of two gender labels (Male or Female) to each reviewer. We set λ0 = λ1 = λ2 = 1 for our experiments. Note that by varying these parameters, one can create the Pareto optimal frontier too.

We run the negative cycle detection algorithm, and the MIQP solver using Gurobi to find the optimum solution. On converging to the optimal solution, we find that all 73 papers receive two male reviewers and two female reviewers, which shows that the method was capable of balancing gender diversity. Each paper receives reviewers from four different clusters. If we only optimize for cluster diversity, it is possible that the gender ratio for individual paper gets skewed. When we run the same model with λg = 0 (no weight to gender diversity), we find that out of 73 papers, 12 papers receive all four reviewers of the same gender and 41 papers receive three reviewers of the same gender. Hence, only 27.3% teams of reviewers are gender balanced. However, one should note that when we do not keep gender as an objective, the resultant allocation is random and different skewness can be observed in different runs based on the initial solution.

Finally, we compare the timing performance of our algorithm with MIQP by changing the number of papers that need to be reviewed on a Dell XPS 13 laptop with i7 processor. For MIQP, we set a maximum run time of four hours (14400 seconds) for Gurobi solver, at which we report the current best MIQP solution. Table 5 shows that for all cases with the number of papers greater than 13, MIQP does not converge within four hours, while our method finds the optimum solution in lesser time. Interestingly, MIQP current solutions are found to be the same as the optimum solution found by our method, which shows that for this application, MIQP was able to search the solution but it was not able to prove that the solution is optimum. In contrast, our method finds the solution faster as well as guarantees that it is optimum.

8 Conclusion &Future Research

In this paper, we proposed the first pseudo-polynomial time algorithms for multi-feature diverse weighted bipartite bmatching-a problem that we also showed is NP-hard. We propose an algorithm that not only guarantees an optimal solution but also converges faster than a proposed approach using a black-box industrial MIQP solver. We demonstrated our results on a dataset for paper reviewer matching. Future work could explore the extension of this method to online diverse matching [Dickerson et al., 2019], where vertices arrive sequentially and must match immediately; this has direct application in advertising, where one could balance notions of reach, frequency, and immediate monetary return. Exploring connections to fairness in machine learning [Grgi´c-Hlaˇca et al., 2018] and hiring [Schumann et al., 2019] by way of diversity are also of immediate interest.

Acknowledgements

We would like to thank anonymous reviewers for their helpful comments. Dickerson was supported by NSF CAREER Award IIS-1846237, DARPA #S4761, NIH NLM-01303901 and a generous gift from Google. Khuller was supported by research awards from Adobe and Amazon. Ahmadi was supported in part by a research award from Amazon. Ahmed and Fuge were supported in part by NSF CMMI-1727849.