# On a generalization of R. Chapman’s “evil determinant”

Li-Yuan Wang, Hai-Liang Wu, He-Xia Ni  (Li-Yuan Wang) School of Physical and
Mathematical Sciences, Nanjing Tech University, Nanjing 211816, People’s
Republic of China<EMAIL_ADDRESS>(Hai-Liang Wu) School of Science,
Nanjing University of Posts and Telecommunications, Nanjing 210023, People’s
Republic of China<EMAIL_ADDRESS>(He-Xia Ni*)Department of Applied
Mathematics, Nanjing Audit University, Nanjing 211815, People’s Republic of
China<EMAIL_ADDRESS>
###### Abstract.

Let $p$ be an odd prime and $x$ be an indeterminate. Recently, Z.-W. Sun
proposed the following conjecture:

$\det\left[x+\left(\frac{j-i}{p}\right)\right]_{0\leq
i,j\leq\frac{p-1}{2}}=\begin{cases}(\frac{2}{p})pb_{p}x-a_{p}&\mbox{if}\
p\equiv 1\ ({\rm{mod}}\ 4),\\\ 1&\mbox{if}\ p\equiv 3\ ({\rm{mod}}\
4),\end{cases}$

where $a_{p}$ and $b_{p}$ are rational numbers related to the fundamental unit
and class number of the real quadratic field $\mathbb{Q}(\sqrt{p})$. In this
paper, we confirm the above conjecture of Sun based on Vsemirnov’s
decomposition of Chapman’s “evil determinant”.

2020 Mathematics Subject Classification. Primary 11C20; Secondary 11L05,
11R18.
Keywords. determinants, Legendre symbol, Gauss sums.
This research was supported by the National Natural Science Foundation of
China (Grant Nos. 12371004, 12201291 and 12101321) and the Natural Science
Foundation of the Higher Education Institutions of Jiangsu Province
(21KJB110001, 21KJB110002).

*Corresponding author.

##  1\. Introduction

The study of determinants involving Legendre symbols is an active topic in
algebra, number theory and combinatorics. Krattenthaler summarized many
results on the evaluation of determinants (see [5, 6]). Let $p$ be an odd
prime and $(\frac{\cdot}{p})$ be the Legendre symbol. Carlitz [2] showed that

$\det\left[\left(\frac{j-i}{p}\right)\right]_{1\leq i,j\leq p-1}=p^{(p-3)/2}.$

In 2004, R. Chapman [3] studied several variants of Carlitz’s results. In
particular, he posed seveal related conjectures. The most famous one is the
“evil determinant conjecture” (see [1, 4] for the motivation of this
conjecture). When $p\equiv 1\ ({\rm{mod}}\ 4)$ we let $\varepsilon_{p}>1$ and
$h_{p}$ denote the fundamental unit and class number of the real quadratic
field $\mathbb{Q}(\sqrt{p})$ respectively. And we write

$\displaystyle\varepsilon_{p}^{(2-(\frac{2}{p}))h_{p}}=a_{p}+b_{p}\sqrt{p}\ $
(1.1)

where $\ a_{p},b_{p}\in\mathbb{Q}$. The “evil determinant conjecture” says
that

$\displaystyle\det\left[\left(\frac{j-i}{p}\right)\right]_{0\leq
i,j\leq\frac{p-1}{2}}=\begin{cases}-a_{p}&\mbox{if}\ p\equiv 1\ ({\rm{mod}}\
4),\\\ 1&\mbox{if}\ p\equiv 3\ ({\rm{mod}}\ 4).\end{cases}$ (1.2)

Chapman could not solve this problem for many years so that he named it “evil
determinant conjecture”. This conjecture was later comfirmed by Vsemirnov [9,
10] with sophisticated matrix decomposition.

In 2019, along this line, Zhi-Wei Sun [7] obtained many revelant results on
this topic. For instance, if $p\equiv 1\ ({\rm{mod}}\ 4)$ is a prime and
$d\in\mathbb{Z}$, Sun showed that

$\det\left[\left(\frac{i+dj}{p}\right)\right]_{0\leq
i,j\leq(p-1)/2}\equiv\bigg{(}\bigg{(}\frac{d}{p}\bigg{)}d\bigg{)}^{(p-1)/4}\frac{p-1}{2}!\
({\rm{mod}}\ p).$

Also, Sun [7] posed some related conjectures for further study. Let $x$ be an
indeterminate. Define

$C(x):=\det\left[x+\left(\frac{j-i}{p}\right)\right]_{0\leq
i,j\leq\frac{p-1}{2}}.$

Recently Sun posed a conjecture on $C(x)$. In this paper we obtain the
following theorem, which confirmed that conjecture.

######  Theorem 1.1.

Let $p$ be an odd prime and $a_{p}$, $b_{p}$ be as (1.1). Then

$C(x)=\begin{cases}(\frac{2}{p})pb_{p}x-a_{p}&\mbox{if}\ p\equiv 1\
({\rm{mod}}\ 4),\\\ 1&\mbox{if}\ p\equiv 3\ ({\rm{mod}}\ 4).\end{cases}$

Note that when we take $x=0$ the above result coincides with (1.2). Our idea
to prove this result is mainly based on Vsemirnov’s decomposition [9, 10] of
$\left[\left(\frac{j-i}{p}\right)\right]_{0\leq i,j\leq(p-1)/2}$. The proof of
Theorem 1.1 will be given in section 2 and section 3.

##  2\. Proof of Theorem 1.1: Case $p\equiv 3\ ({\rm{mod}}\ 4)$

We begin with a lemma we shall use in the proof.

######  Lemma 2.1 (The Matrix Determinant Lemma).

Let $H$ be an $n\times n$ matrix, and let ${\bf u},{\bf v}$ be two
$n$-dimensional column vectors. Then

$\det(H+{\bf u}{\bf v}^{T})=\det H+{\bf v}^{T}{\rm adj}(H){\bf u},$

where ${\rm adj}(H)$ is the adjugate matrix of $H$ and ${\bf v}^{T}$ is the
transpose of ${\bf v}$.

The proof of this lemma can be found in [8].

Let $n=(p-1)/2$ throuthout the proof. We first consider the case $p\equiv 3\
({\rm{mod}}\ 4)$.

Proof of Theorem 1.1: Case $p\equiv 3\ ({\rm{mod}}\ 4)$. Let ${\bf
u}=(1,1,\ldots,1)^{T}$ be a column vector of length $n+1$ and ${\bf
v}=x\cdot{\bf u}$. By Lemma 2.1

$\det(C(x))=\det(C)+x\cdot{\bf u}^{T}{\rm adj}(C){\bf u}.$

In view of (1.2), it is sufficient to show that ${\bf u}^{T}{\rm adj}(C){\bf
u}=0$. For any matrix $A=[a_{ij}]_{0\leq i,j\leq m}$, we use ${\rm
adj}(A)=[A_{ji}]_{0\leq i,j\leq m}$ to denote its adjugate matrix. Then ${\rm
adj}(C)=[C_{ji}]_{0\leq i,j\leq\frac{p-1}{2}}$ and

${\bf u}^{T}{\rm adj}(C){\bf
u}=\sum_{k=0}^{n}\sum_{l=0}^{n}C_{kl}=\sum_{k=0}^{(p-3)/4}\sum_{l=0}^{n}C_{kl}+C_{n-k\;n-l}.$

If we let $M_{i,j}$ denote the $(i,j)$ minor of $C$ (i.e., the determinant of
the submatrix of $C$ formed by deleting the $i$th row and $j$th column) then

$C_{kl}=(-1)^{k+l}M_{k,l}=(-1)^{k+l}\det\left[\left(\frac{j-i}{p}\right)\right]_{0\leq
i,j\leq n\atop i\neq k,j\neq l},$

and

$C_{n-k\;n-l}=(-1)^{n-k+n-l}M_{n-k,n-l}=(-1)^{k+l}\det\left[\left(\frac{j-i}{p}\right)\right]_{0\leq
i,j\leq n\atop i\neq n-k,j\neq n-l}.$

Note that

$\displaystyle\det\left[\left(\frac{j-i}{p}\right)\right]_{0\leq i,j\leq
n\atop i\neq n-k,j\neq n-l}$
$\displaystyle=(-1)^{\lfloor\frac{p-1}{4}\rfloor}\det\left[\left(\frac{n-j-i}{p}\right)\right]_{0\leq
i,j\leq n\atop i\neq n-k,j\neq l}$
$\displaystyle=(-1)^{\lfloor\frac{p-1}{4}\rfloor}\cdot(-1)^{\lfloor\frac{p-1}{4}\rfloor}\det\left[\left(\frac{n-j-(n-i)}{p}\right)\right]_{0\leq
i,j\leq n\atop i\neq k,j\neq l}$
$\displaystyle=\det\left[-\left(\frac{j-i}{p}\right)\right]_{0\leq i,j\leq
n\atop i\neq k,j\neq l}$
$\displaystyle=(-1)^{n}\det\left[\left(\frac{j-i}{p}\right)\right]_{0\leq
i,j\leq n\atop i\neq k,j\neq l}$
$\displaystyle=-\det\left[\left(\frac{j-i}{p}\right)\right]_{0\leq i,j\leq
n\atop i\neq k,j\neq l}.$

Hence

$C_{kl}+C_{n-k\;n-l}=0$

for any $0\leq k\leq(p-3)/4$ and $0\leq l\leq n$. It follows that

${\bf u}^{T}{\rm adj}(C){\bf u}=0.$

This completes the proof of Theorem 1.1 for $p\equiv 3\ ({\rm{mod}}\ 4)$. ∎

##  3\. Proof of Theorem 1.1: Case $p\equiv 1\ ({\rm{mod}}\ 4)$

In this section we deal with the case $p\equiv 1\ ({\rm{mod}}\ 4)$. We begin
with the following lemmas.

######  Lemma 3.1.

([10, Theorem 3]). Let $u_{i},v_{j}(1\leq i,j\leq m)$ be complex numbers such
that $u_{i}v_{j}\neq-1$. Then

$\displaystyle\det\bigg{[}\frac{u_{i}+v_{j}}{1+u_{i}v_{j}}\bigg{]}_{1\leq
i,j\leq m}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\bigg{(}\prod_{i=1}^{m}(1+u_{i})(1+v_{i})+(-1)^{m}\prod_{i=1}^{m}(1-u_{i})(1-v_{i})\bigg{)}$
$\displaystyle\quad\times\prod_{1\leq i<j\leq
m}\bigg{(}(u_{i}-u_{j})(v_{j}-v_{i})\bigg{)}\prod_{i=1}^{m}\prod_{j=1}^{m}(1+u_{i}v_{j})^{-1}.$

Using essentially the same method appeared in the proof of [10, Lemma 2], it
is easy to get the following result.

######  Lemma 3.2.

Let notations be as above. Then

$\displaystyle\frac{1}{2}\bigg{(}\prod_{j=1}^{n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{)}^{2}+\prod_{j=1}^{n}\bigg{(}1-\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{)}^{2}\bigg{)}=(-1)^{n/2}\zeta^{n(n+1)/2}b_{p}p.$

Proof of Theorem 1.1: Case $p\equiv 1\ ({\rm{mod}}\ 4)$. By similar methods
appeared in the proof of the case $p\equiv 3\ ({\rm{mod}}\ 4)$, it is
sufficient to show that

${\bf u}^{T}{\rm adj}(C){\bf u}=\bigg{(}\frac{2}{p}\bigg{)}pb_{p}.$ (3.1)

For convenience, we introduce Vsemivnov’s notations [10]. Let $\zeta=e^{2\pi
i/p}$ and define square matrices $U,V,D$ of order $n+1$ with $(i,j)$ entry as
follows:

$\displaystyle u_{ij}=$
$\displaystyle\frac{(\frac{i}{p})\zeta^{-j-2i}+(\frac{j}{p})\zeta^{-2j-i}}{\zeta^{-i-j}+(\frac{i}{p})(\frac{j}{p})},\quad
0\leq i,j\leq n,$ $\displaystyle v_{ij}=$ $\displaystyle\zeta^{2ij},\quad
0\leq i,j\leq n,$ $\displaystyle d_{ii}=$ $\displaystyle\prod_{0\leq k\leq
n\atop k\neq i}\frac{1}{\zeta^{2i}-\zeta^{2k}},\quad 0\leq i\leq n,$
$\displaystyle d_{ij}=$ $\displaystyle 0,\quad 0\leq i\neq j\leq n.$

Vsemivnov [10, Theorem 2] proved that

$C=\bigg{(}\frac{2}{p}\bigg{)}\sqrt{p}\zeta^{(p-1)/4}\cdot VDUDV.$

By this we have

$\displaystyle{\bf u}^{T}{\rm adj}(C){\bf u}$
$\displaystyle=\bigg{(}\frac{2}{p}\bigg{)}^{n}(\sqrt{p})^{n}\zeta^{\frac{n^{2}}{2}}\cdot{\bf
u}^{T}\cdot{\rm adj}V\cdot{\rm adj}D\cdot{\rm adj}U\cdot{\rm adj}D\cdot{\rm
adj}(V)\cdot{\bf u}$
$\displaystyle=(\sqrt{p})^{n}\zeta^{\frac{n^{2}}{2}}\cdot{\bf u}^{T}\cdot{\rm
adj}V\cdot{\rm adj}D\cdot{\rm adj}U\cdot{\rm adj}D\cdot{\rm adj}(V)\cdot{\bf
u}.$

For any matrix $A$, we let $A^{(k)}$ denote the matrix obtained from $A$ via
replacing all entries in the $(k+1)$-th row by $1$. Then

$\displaystyle{\bf u}^{T}\cdot{\rm adj}V=$
$\displaystyle(1,1,\ldots,1)\cdot{\rm adj}V$ $\displaystyle=$
$\displaystyle(1,1,\ldots,1)\cdot[V_{ji}]_{0\leq i,j\leq n}$ $\displaystyle=$
$\displaystyle\bigg{(}\sum_{k=0}^{n}V_{0k},\sum_{k=0}^{n}V_{1k},\ldots,\sum_{k=0}^{n}V_{nk}\bigg{)}$
$\displaystyle=$ $\displaystyle\bigg{(}\det V^{(0)},\det V^{(1)},\ldots,\det
V^{(n)}\bigg{)}.$

Since each element of the first row of $V$ is $1$, we have $\det V^{(0)}=\det
V$ and $\det V^{(k)}=0$ for $1\leq k\leq n$. Thus

$\displaystyle{\bf u}^{T}\cdot{\rm adj}V=\det V\cdot(1,0,0,\ldots,0).$

Recall that $D$ is a diagonal matrix with $(i+1)$-th diagonal element
$d_{ii}$. Hence

${\rm adj}D=\det D\cdot D^{-1}=\det
D\cdot\left(\begin{array}[]{cccccccc}\frac{1}{d_{00}}&&&\\\
&\frac{1}{d_{11}}&&\\\ &&\ddots&\\\ &&&\frac{1}{d_{nn}}\\\
\end{array}\right).$

It follows that

$\displaystyle{\bf u}^{T}\cdot{\rm adj}V\cdot{\rm adj}D=\frac{\det V\cdot\det
D}{d_{00}}\cdot(1,0,0,\ldots,0).$

Note that $V$, $D$, ${\rm adj}V$ and ${\rm adj}D$ are symmetric matrices.
Hence

${\rm adj}D\cdot{\rm adj}V\cdot{\bf u}=\frac{\det V\cdot\det
D}{d_{00}}\cdot(1,0,0,\ldots,0)^{T}.$

Consequently,

$\displaystyle{\bf u}^{T}\cdot{\rm adj}V\cdot{\rm adj}D\cdot{\rm
adj}U\cdot{\rm adj}D\cdot{\rm adj}(V)\cdot{\bf u}$ $\displaystyle=\frac{(\det
V)^{2}\cdot(\det D)^{2}}{d_{00}^{2}}\cdot(1,0,0,\ldots,0)\cdot{\rm
adj}U\cdot(1,0,0,\ldots,0)^{T}$ $\displaystyle=\frac{(\det V)^{2}\cdot(\det
D)^{2}}{d_{00}^{2}}\cdot(U_{00},U_{10},\ldots,U_{n0})\cdot(1,0,0,\ldots,0)^{T}$
$\displaystyle=\frac{(\det V)^{2}\cdot(\det D)^{2}}{d_{00}^{2}}\cdot U_{00}.$

By (3) we have

$\displaystyle{\bf u}^{T}{\rm adj}(C){\bf
u}=(\sqrt{p})^{n}\zeta^{\frac{n^{2}}{2}}\cdot\frac{(\det V)^{2}\cdot(\det
D)^{2}}{d_{00}^{2}}\cdot U_{00}.$

Recall that

$\displaystyle\frac{1}{d_{00}^{2}}=$ $\displaystyle\prod_{0<k\leq
n}(1-\zeta^{2k})^{2}$ $\displaystyle=$
$\displaystyle\prod_{k=1}^{n}(1-\zeta^{2k})\prod_{k=1}^{n}(1-\zeta^{2k})$
$\displaystyle=$
$\displaystyle(-1)^{n}\cdot\prod_{k=1}^{n}\zeta^{2k}\cdot\prod_{k=1}^{n}(1-\zeta^{-2k})\cdot\prod_{k=1}^{n}(1-\zeta^{2k})$
$\displaystyle=$
$\displaystyle\zeta^{n(n+1)}\cdot\prod_{k=1}^{n}(1-\zeta^{-2k})\cdot\prod_{k=1}^{n}(1-\zeta^{2k})$
$\displaystyle=$
$\displaystyle\zeta^{n(n+1)}\cdot\prod_{k=1}^{p-1}(1-\zeta^{k})$
$\displaystyle=$ $\displaystyle p\zeta^{n(n+1)}.$

Thus,

$\displaystyle{\bf u}^{T}{\rm adj}(C){\bf
u}=p^{\frac{p+3}{4}}\zeta^{\frac{n^{2}+n}{2}}\cdot(\det V)^{2}\cdot(\det
D)^{2}\cdot U_{00}.$ (3.3)

We next evaluate $U_{00}$. One can verify that

$\displaystyle U_{00}$ $\displaystyle=\det[u_{ij}]_{1\leq i,j\leq n}$
$\displaystyle=\det\bigg{[}\frac{(\frac{i}{p})\zeta^{-j-2i}+(\frac{j}{p})\zeta^{-2j-i}}{\zeta^{-i-j}+(\frac{i}{p})(\frac{j}{p})}\bigg{]}_{1\leq
i,j\leq n}$
$\displaystyle=\det\bigg{[}\frac{(\frac{i}{p})\zeta^{-i}+(\frac{j}{p})\zeta^{-j}}{1+(\frac{i}{p})(\frac{j}{p})\zeta^{i+j}}\bigg{]}_{1\leq
i,j\leq n}$
$\displaystyle=\det\bigg{[}\frac{(\frac{i}{p})\zeta^{i}+(\frac{j}{p})\zeta^{j}}{1+(\frac{i}{p})(\frac{j}{p})\zeta^{i+j}}\cdot\frac{1}{(\frac{i}{p})(\frac{j}{p})\zeta^{i+j}}\bigg{]}_{1\leq
i,j\leq n}$ $\displaystyle=\prod_{1\leq i\leq
n}\frac{1}{(\frac{i}{p})\zeta^{i}}\cdot\prod_{1\leq j\leq
n}\frac{1}{(\frac{j}{p})\zeta^{j}}\cdot\det\bigg{[}\frac{(\frac{i}{p})\zeta^{i}+(\frac{j}{p})\zeta^{j}}{1+(\frac{i}{p})\zeta^{i}(\frac{j}{p})\zeta^{j}}\bigg{]}_{1\leq
i,j\leq n}$
$\displaystyle=\zeta^{-\frac{p-1}{4}}\cdot\det\bigg{[}\frac{(\frac{i}{p})\zeta^{i}+(\frac{j}{p})\zeta^{j}}{1+(\frac{i}{p})\zeta^{i}(\frac{j}{p})\zeta^{j}}\bigg{]}_{1\leq
i,j\leq n}.$ (3.4)

Take $m=n=(p-1)/2$ and $u_{i}=v_{i}=(\frac{i}{p})\zeta^{i}$ in Lemma 3.1 and
by Lemma 3.2 we deduce that

$\displaystyle\det\bigg{[}\frac{(\frac{i}{p})\zeta^{i}+(\frac{j}{p})\zeta^{j}}{1+(\frac{i}{p})\zeta^{i}\cdot(\frac{j}{p})\zeta^{j}}\bigg{]}_{1\leq
i,j\leq n}$
$\displaystyle=\frac{1}{2}\bigg{(}\prod_{i=1}^{n}(1+u_{i})(1+v_{i})+\prod_{i=1}^{n}(1-u_{i})(1-v_{i})\bigg{)}\cdot$
$\displaystyle\prod_{1\leq i<j\leq
n}\bigg{(}(u_{i}-u_{j})(v_{j}-v_{i})\bigg{)}\prod_{i=1}^{n}\prod_{j=1}^{n}(1+u_{i}v_{j})^{-1}$
$\displaystyle=(-1)^{n/2}\zeta^{n(n+1)/2}b_{p}p\cdot\prod_{1\leq i<j\leq
n}\bigg{(}(u_{i}-u_{j})(u_{j}-u_{i})\bigg{)}\prod_{i=1}^{n}\prod_{j=1}^{n}(1+u_{i}u_{j})^{-1}$
$\displaystyle=(-1)^{n/2+\binom{n}{2}}\zeta^{n(n+1)/2}b_{p}p\cdot\prod_{1\leq
i<j\leq n}(u_{i}-u_{j})^{2}\prod_{i=1}^{n}\prod_{j=1}^{n}(1+u_{i}u_{j})^{-1}$
$\displaystyle=\zeta^{n(n+1)/2}b_{p}p\cdot\prod_{1\leq i<j\leq
n}(u_{i}-u_{j})^{2}\prod_{i=1}^{n}\prod_{j=1}^{n}(1+u_{i}u_{j})^{-1}$
$\displaystyle=\zeta^{n(n+1)/2}b_{p}p\cdot\prod_{1\leq i<j\leq
n}\bigg{(}\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}-\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{2}\prod_{i=1}^{n}\prod_{j=1}^{n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{-1}.$

Define

$f_{1}=\prod_{1\leq i<j\leq
n}\bigg{(}\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}-\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}$

and

$f_{2}=\prod_{1\leq i<j\leq
n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}.$

Then

$\displaystyle\prod_{1\leq i<j\leq
n}\bigg{(}\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}-\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{2}\prod_{i=1}^{n}\prod_{j=1}^{n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{-1}$
$\displaystyle=f_{1}^{2}\prod_{i=1}^{n}\prod_{j=1}^{n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{-1}$
$\displaystyle=f_{1}^{2}\prod_{1\leq i=j\leq
n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{-1}\prod_{1\leq
i<j\leq
n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{-1}$
$\displaystyle\quad\times\prod_{1\leq j<i\leq
n}\bigg{(}1+\bigg{(}\frac{j}{p}\bigg{)}\zeta^{j}\bigg{(}\frac{i}{p}\bigg{)}\zeta^{i}\bigg{)}^{-1}$
$\displaystyle=f_{1}^{2}\ f_{2}^{-2}\prod_{j=1}^{n}(1+\zeta^{2j})^{-1}.$

By [10, Corollary 2 (4.6)] we see that

$\prod_{j=1}^{n}(1+\zeta^{2j})=\zeta^{n(n+1)/2}\bigg{(}\frac{2}{p}\bigg{)}.$
(3.7)

Combining (3), (3) with (3.7), we obtain

$\displaystyle\det\bigg{[}\frac{(\frac{i}{p})\zeta^{i}+(\frac{j}{p})\zeta^{j}}{1+(\frac{i}{p})\zeta^{i}(\frac{j}{p})\zeta^{j}}\bigg{]}_{1\leq
i,j\leq n}=pb_{p}\bigg{(}\frac{2}{p}\bigg{)}\cdot f_{1}^{2}\cdot f_{2}^{-2}.$
(3.8)

By (3) and (3.8) we have

$\displaystyle
U_{00}=\bigg{(}\frac{2}{p}\bigg{)}pb_{p}\cdot\zeta^{-\frac{p-1}{4}}\cdot
f_{1}^{2}\cdot f_{2}^{-2}.$

Combining (3.3) with the above equalities, we get

$\displaystyle{\bf u}^{T}{\rm adj}(C){\bf
u}=\bigg{(}\frac{2}{p}\bigg{)}pb_{p}\cdot\zeta^{\frac{(p-1)^{2}}{8}}\cdot
p^{\frac{p+3}{4}}\cdot(\det V)^{2}\cdot(\det D)^{2}\cdot f_{1}^{2}\cdot
f_{2}^{-2}.$ (3.9)

By [10, Eq. (4.10)] one may verify that

$\displaystyle 1$
$\displaystyle=\zeta^{(n+1)(p-1)/4}\bigg{(}\bigg{(}\frac{2}{p}\bigg{)}\sqrt{p}\bigg{)}^{n+2}\cdot(\det
V)^{2}\cdot(\det D)^{2}\cdot(\det G)^{-2}\cdot f_{1}^{2}\cdot f_{2}^{-2}$
$\displaystyle=\zeta^{-\frac{p^{2}-1}{8}}\cdot p^{\frac{p+3}{4}}\cdot(\det
V)^{2}\cdot(\det D)^{2}\cdot f_{1}^{2}\cdot f_{2}^{-2}$

where

$(\det
G)^{2}=\bigg{(}\prod_{j=1}^{n}(\frac{j}{p})\zeta^{j}\bigg{)}^{2}=\zeta^{n(n+1)}=\zeta^{\frac{p^{2}-1}{4}}.$

Hence

$\displaystyle\zeta^{\frac{(p-1)^{2}}{8}}\cdot p^{\frac{p+3}{4}}\cdot(\det
V)^{2}\cdot(\det D)^{2}\cdot f_{1}^{2}\cdot
f_{2}^{-2}=\zeta^{\frac{(p-1)^{2}}{8}+\frac{p^{2}-1}{8}}=1.$ (3.10)

The last equality follows from

$\frac{(p-1)^{2}}{8}+\frac{p^{2}-1}{8}=p\cdot\frac{p-1}{4}\equiv 0\
({\rm{mod}}\ p).$

Now (3.1) follows from (3.9) and (3.10).

This completes the proof of Theorem 1.1.∎

## References

  * [1] P. J. Cameron and D. B. West, Research problems from the 20th British Combina- torial Conference, Discrete Math. 308 (2008), 621–630.
  * [2] L. Carlitz, Some cyclotomic matrices, Acta Arith. 5 (1959), 293–308.
  * [3] R. Chapman, Determinants of Legendre symbol matrices, Acta Arith. 115 (2004), 231–244.
  * [4] R. Chapman, My evil determinant problem, preprint, December 12, 2012, available from http://empslocal.ex.ac.uk/people/staff/rjchapma/etc/evildet.pdf.
  * [5] C. Krattenthaler, Advanced Determinant Calculus. In: Foata D., Han GN. (eds) The Andrews Festschrift. Springer, Berlin, Heidelberg 2001.
  * [6] C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68–166.
  * [7] Z.-W. Sun, On some determinants with Legendre symbols entries, Finite Fields Appl. 56 (2019), 285–307.
  * [8] R. Vrabel, A note on the matrix determinant lemma, Int. J. Pure Appl. Math. 111 (2016), 643–646.
  * [9] M. Vsemirnov, On the evaluation of R. Chapman’s “evil determinant”, Linear Algebra Appl. 436 (2012), 4101–4106.
  * [10] M. Vsemirnov, On R. Chapman’s “evil determinant”: case $p\equiv 1\ ({\rm{mod}}\ 4)$, Acta Arith. 159 (2013), 331–344.


# Team Formation amidst Conflicts

Iasonas Nikolaou  1234-5678-9012 Boston UniversityBostonUSA<EMAIL_ADDRESS>and  Evimaria Terzi  Boston UniversityBostonUSA<EMAIL_ADDRESS>
(2024)

###### Abstract.

In this work, we formulate the problem of _team formation amidst conflicts_.
The goal is to assign individuals to tasks, with given capacities, taking into
account individuals’ task preferences and the conflicts between them. Using
dependent rounding schemes as our main toolbox, we provide efficient
approximation algorithms. Our framework is extremely versatile and can model
many different real-world scenarios as they arise in educational settings and
human-resource management. We test and deploy our algorithms on real-world
datasets and we show that our algorithms find assignments that are better than
those found by natural baselines. In the educational setting we also show how
our assignments are far better than those done manually by human experts. In
the human-resource management application we show how our assignments increase
the diversity of teams. Finally, using a synthetic dataset we demonstrate that
our algorithms scale very well in practice.

team formation, conflicts, task assignment, diversity

††journalyear: 2024††copyright: rightsretained††conference: Proceedings of the
ACM Web Conference 2024; May 13–17, 2024; Singapore, Singapore††booktitle:
Proceedings of the ACM Web Conference 2024 (WWW ’24), May 13–17, 2024,
Singapore, Singapore††doi: 10.1145/3589334.3645444††isbn:
979-8-4007-0171-9/24/05††ccs: Theory of computation Social networks

##  1\. Introduction

In large project-based classes instructors often need to create _teams_ of
students and assign them to a finite number of projects they have available.
Students are happy if they are in a team with friends and they work on a
project they like. Additionally, student teams are efficient if there are no
time conflicts between the team members; i.e., conflicts that stem from their
class schedule. Traditionally, such assignments are done in an adhoc manner or
manually by some admin who can spend several days on the task.

Motivated by such applications in the education domain, we formally define the
above problem as a combinatorial optimization problem. For this, we assume two
inputs: the _preference graph_ and the _conflict graph_. The former captures
the preferences of users to projects; this is a bipartite graph with edge
weights that are proportional to how much a student likes a project. The
latter captures the conflicts between students, i.e., there is a (weighted)
edge between two students if they are incompatible. Our goal is to find an
assignment of students to projects such that every student is assigned to one
project and every project is not assigned more students than its capacity. The
objective is to maximize the sum of the weights of the edges of the preference
graph that participate in the assignment and and the sum of the weights of the
conflict edges across the formed teams. Students assigned to the same project
form a team so we call this problem the Team Formation amidst Conflicts (TFC)
problem and we show it is NP-hard.

In this paper, we present an algorithmic framework for approximating TFC. This
framework, consists of two steps: first, our objective is replaced by a
concave objective – which can be optimized in polynomial time and produce a
fractional solution. Then, the fractional solution is rounded, using
dependent-rounding techniques (Ageev and Sviridenko, 2004; Gandhi et al.,
2002). For our framework to work we need the original objective and its
concave relaxation to match on integral inputs.

This general framework is not new. In fact, it is inspired by the _Max-
$k$-Cut with given part sizes_ problem (Ageev and Sviridenko, 2004). In fact,
our problem is identical to the _Max- $k$-Cut with given part sizes_, except
for the fact that we also have an additional linear term in our objective. We
show that their approximation algorithm can be applied to our problem. Our
contribution is a much more efficient randomized algorithm with better
approximation ratio on expectation.

To the best of our knowledge the dependent-rounding techniques we use here,
such as pipage and randomized pipage, have not been widely used in practical
applications; they primarily stem from work in theoretical computer science
(Ageev and Sviridenko, 2004; Chekuri et al., 2010). We see the deployment of
these techniques in practice as a contribution by itself.

Using real, anonymized data, from large classes 111We obtained an IRB
exemption to use the anonymized version of this data., we demonstrate that our
algorithms work extremely well in practice. In our experiments, we show that
the solutions we obtain are much better compared to the manual solutions
produced by a course admin across different dimensions and metrics.

Our problem formulation is general and goes beyond educational settings. For
example, we can use our framework in human-resource management in order to
increase the diversity of departments in companies; depending on the dimension
across which we want to diversify we can appropriately define the conflict
graph. In our experiments, we show how to achieve gender diversity in a
company’s departments using this idea.

The generality of our framework calls for efficient algorithms. Part of our
contribution is a set of speedup techniques that allow us to apply our
approximation algorithms to reasonably large data. In our experimental
evaluation we demonstrate that these techniques work extremely well in
practice.

Discussion: We note here that it was a design decision from our part to
consider the conflict graph and maximize conflicts across teams (instead of
friends within teams). We believe that this choice gives us greater modeling
flexibility to apply our model to a variety of settings. For example, the
conflict graph better models time conflicts among collaborators as well as
diversity constraints.

##  2\. Related work

To the best of our knowledge, we are the first to define and approximate the
TFC problem. However, our work is related to works in _team formation_ , in
the data-mining literature, as well as other _assignment_ and _clustering_
problems, in the theoretical computer science literature. We review these
works below.

Team formation: In terms of application, our work belongs to the team-
formation literature (Anagnostopoulos et al., 2010, 2018; Lappas et al., 2009;
Vombatkere and Terzi, 2023; Kargar et al., 2013; Majumder et al., 2012). Most
of these works consider the problem of assigning groups of individuals to
tasks (one group per task) such that the tasks are completed and some
objective (usually related to the well-functioning of the team or the well-
being of the individuals) is optimized. Our problem is a partitioning problem
and as such is much more complicated than problems of finding a good team for
each available task. Additionally, in many of the existing works the objective
function has a well-defined structure (e.g., is monotone and submodular,
concave). Our objective does not have such a structure and while this gives us
modeling power, optimizing it requires more advanced techniques.

Partitioning problems: The _Max- $k$-Cut with given part sizes_ problem (Ageev
and Sviridenko, 2004) served as an inspiration for our model. In fact, our
$1/2$-approximation algorithm is a very close variant of the algorithm
presented there. However, our objective function is slightly different from
the one defined by Ageev et al. – due to an additional linear term. This
allows us to design algorithms tailored to our problem, which achieve better
approximation ratios under certain assumptions. Additionally, we focused on
developing scalable algorithms as the running time of the algorithm proposed
by Ageev et al. was not a computationally feasible approach.

Clustering problems: One can view our problem as a clustering problem with
capacity constraints (Zhu et al., 2010; Negreiros and Palhano, 2006). Our
model, however, is quite different from these works both in the objective
function and the constraints.

Assignment problems: Our problem can be viewed as a generalization of the
_weighted assignment_ problem (Kuhn, 1955), where the goal is to assign
individuals to tasks taking into account the task preferences of individuals.
In our problem, apart from task preferences, we also have a graph capturing
the relationships (or conflicts) between individuals. This additional
structure increases the complexity of the problem significantly. Our problem
is also related to the famous _stable marriage_ (McVitie and Wilson, 1971)
problem and its variants (Gale and Shapley, 1962; Gusfield and Irving, 1989).
However, we don’t look for a stable matching. Instead, our goal is to optimize
an objective function capturing the overall satisfaction of individuals.

The metric-labeling problem: A minimization version of our problem is the
_metric-labeling_ problem (Kleinberg and Tardos, 2002), where the goal is to
assign one of $k$ labels to each node (i.e., partition the nodes). Every
assignment incurs assignment costs (based on the choice of label for each
node) and separation costs (based on the choice of labels for ”related”
nodes). In the capacitated version of metric-labeling (Andrews et al., 2011)
we are also given a capacity for each partition. The main disadvantage of the
algorithm developed for this version (Andrews et al., 2011) is that the
capacity constraints are violated by a multiplicative factor. Also, the
algorithm only works for labels with uniform capacities. Finally, the
approximation factor of the proposed algorithm depends on the number of labels
(i.e. tasks). Defining TFC as a maximization problem allows us to overcome all
of the above disadvantages.

##  3\. Problem definition

In this section, we provide the necessary notation and we formally define the
problem we solve in this paper.

Notation: Throughout the paper, we assume that we are given a weighted
(undirected) graph $G=(V,E_{G},w)$ with $w:E_{G}\rightarrow\mathbb{R}_{\geq
0}$. More specifically, each node $v\in V$ corresponds to an individual; the
weight $w_{uv}$ of an edge $(u,v)\in E_{G}$ captures the degree of conflict
between individuals $u$ and $v$. We call graph $G$ the _conflict graph_.

In addition to the conflict graph $G$, we also assume a preference graph $R$,
which is a _bipartite graph_ , i.e., $R=(V,T,E_{R},c)$. The one side of the
graph corresponds to individuals ($V$), the other side to items or tasks $T$.
The edges ($E_{R}$) capture the preferences of individuals to projects. More
specifically $c:V\times T\rightarrow\mathbb{R}_{\geq 0}$ is a _preference_
function, where $c_{vt}$ captures the satisfaction of individual $v\in V$ when
assigned to task $t\in T$. Without loss of generality we assume that $0\leq
c_{ut}\leq 1$.

Throughout, we assume that each individual $v\in V$ is assigned to exactly one
task and that each task $t\in T$ has _capacity_ $p_{t}$, which is task-
specific.

The Team Formation amidst Conflicts problem: Given the above, our goal is to
assign individuals to tasks such that the overall satisfaction of individuals
is maximized; the satisfaction of each individual is measured by how much they
like the task they are assigned to and the lack of conflicts with the other
individuals assigned to the same task. We capture this intuition formally in
the form of a (quadratic) program. For this, we define binary variables
$x_{vt}$ such that $x_{vt}=1$ if individual $v$ is assigned to task $t$ and
$x_{vt}=0$ otherwise. Thus, our goal is the following:

(1) max $\displaystyle F(\mathbf{x})=\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}+\sum_{(u,v)\in E_{G}}w_{uv}(1-\sum_{t\in T}x_{ut}x_{vt})$ (2)
s.t. $\displaystyle\sum_{t\in T}x_{vt}=1,\forall v\in V$ (3)
$\displaystyle\sum_{v\in V}x_{vt}\leq p_{t},\forall t\in T$ (4) $\displaystyle
x_{vt}\in\\{0,1\\},\forall v\in V,\forall t\in T$

We call the problem captured by the above program Team Formation amidst
Conflicts or TFC for short. The linear term of the objective captures the
satisfaction of assigning individuals to tasks and we call it the _task
satisfaction term_ : $F_{R}=\sum_{v\in V}\sum_{t\in T}c_{vt}x_{vt}$. The
quadratic term captures conflicts in the following sense. The objective
increases by $w_{uv}$ whenever there is conflict between individuals $u$ and
$v$ and they are assigned to different tasks. We call this term the _social
satisfaction term_ , i.e., $F_{G}=\sum_{(u,v)\in E_{G}}w_{uv}(1-\sum_{t\in
T}x_{ut}x_{vt})$; this term models Max-k-Cut with given sizes of parts (Ageev
and Sviridenko, 2004).

As far as the constraints are concerned: the first constraint enforces that
every individual is assigned to exactly one task while the second constraint
enforces that we assign at most $p_{t}$ individuals to task $t\in T$; $p_{t}$
is the capacity of tasks. Observe that our problem as represented above is a
quadratic program with integer constraints and the objective function $F$ is
non-convex. This observation hints that the problem may be computationally
hard. In fact, we have the following result regarding the hardness of TFC:

###### Lemma 0.

The Team Formation amidst Conflicts problem is NP-hard.

The proof stems from the fact that our problem includes the Max-Cut problem
(Karp, 2010), which is NP-hard. To see this, consider the instance of our
problem that has two tasks $T=\\{t_{1},t_{2}\\}$ such that
$p_{t_{1}}=p_{t_{2}}=|V|$. Set $c_{vt}=0,\forall v\in V,\forall t\in T$. This
is indeed an instance of the Max-Cut problem; this observation concludes the
proof of Lemma 1.

An interesting question is what is the value of the hyperparameter $\lambda$
in the linear term and how one should go about setting it. Observe that
$\lambda$ balances the relative importance of task preferences and conflicts;
when $\lambda=0$, the linear term vanishes and we only optimize for conflicts.
As $\lambda$ grows task preferences become dominant. In general, tuning the
hyperparameter is application specific. In Section 4.3, we discuss how we tune
$\lambda$ in practice.

##  4\. Algorithms

In this section, we provide approximation algorithms for the TFC problem. Our
approach for solving this problem is the following: first, we will find a
“nice”, i.e., _concave_ , relaxation of $F$, which we will call $L$. Then, we
will optimize $L$ in the fractional domain. That is, we transform the original
TFC problem described in Equations (1)-(4) to the following concave program:

(5) max $\displaystyle L(\mathbf{x})$ (6) s.t. $\displaystyle\sum_{t\in
T}x_{vt}=1,\forall v\in V$ (7) $\displaystyle\sum_{v\in V}x_{vt}\leq
p_{t},\forall t\in T$ (8) $\displaystyle 0\leq x_{vt}\leq 1,\forall v\in
V,\forall t\in T$

We call this problem Relaxed-TFC and it is clearly very similar to the TFC
problem except for two important differences: the objective $F$ is substituted
by its relaxation $L$. Also, the integrality constraints are substituted by
the corresponding fractional constraints. The relaxations of $F$ we propose
have the following two properties, which are key for the results we propose:

###### Property 1.

$L(\mathbf{x})$ is _concave_.

###### Property 2.

For every $\mathbf{x}\in\\{0,1\\}^{|V|\times|T|}:F(\mathbf{x})=L(\mathbf{x})$.
I.e., the original function and the relaxation agree on the integral values of
$\mathbf{x}$.

Given that $L$ is concave and the constraints are linear, Relaxed-TFC can be
solved using _gradient ascent_ (Boyd and Vandenberghe, 2004).

Finally, by using appropriate rounding techniques we transform our solution to
an integral solution. This general algorithm, which we call Relax-Round is
described in Algorithm 1. Relax-Round serves as a template for the
approximation algorithms we develop.

We present two algorithms that use two different concave relaxations and
rounding schemes, which in turn give different approximation guarantees and
come with their own running-time implications.

Algorithm 1 Relax-Round: A general approximation algorithm for the TFC
problem.

Objective function $F$, Rounding scheme $\Xi$

Relax: Given $F$ construct a concave fractional relaxation $L$ such that:
$F(\mathbf{x})=L(\mathbf{x})$ for all integral $\mathbf{x}$.

Optimize:
$\mathbf{y}^{\ast}=\operatorname*{arg\,max}_{\mathbf{y}}L(\mathbf{y})$

Round: $\mathbf{x}=\Xi(\mathbf{y}^{\ast})$

###  4.1. A deterministic $\frac{1}{2}$ \- approximation algorithm

We start by describing a $\frac{1}{2}$-approximation algorithm for the TFC
problem. This algorithm was first introduced by Ageev et al. (Ageev and
Sviridenko, 2004) for the _Max- $k$-Cut with given part sizes_. However, we
present it here for completeness. We call this algorithm Pipage, because it
uses _pipage_ rounding (Ageev and Sviridenko, 2004) in order to instantiate
Relax-Round. We describe the concave relaxation $L_{1}$ and pipage rounding
below.

The $L_{1}$ concave relaxation:

(9) $L_{1}(\mathbf{x})=\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}+\sum_{(u,v)\in
E_{G}}w_{uv}\min\left(1,\min_{t}(2-x_{ut}-x_{vt})\right).$

We have the following for $L_{1}$:

###### Proposition 0 ((Ageev and Sviridenko, 2004)).

$L_{1}$ satisfies Properties 1 and 2.

The proof of Proposition 1 relies on simple algebra (see (Ageev and
Sviridenko, 2004)) and thus omitted.

Pipage rounding: pipage rounding takes a fractional solution $\mathbf{y}$ of
the TFC problem and transforms it into an integral solution $\mathbf{x}$. The
following is a high-level description of the algorithm. For a more thorough
analysis and description of the algorithm we refer the reader to Appendix C.1
and the original paper (Ageev and Sviridenko, 2004).

Pipage rounding is an iterative algorithm; at each iteration the current
fractional solution $\mathbf{y}$ is transformed into a new solution
$\mathbf{y}^{\prime}$ with smaller number of non-integral components.
Throughout, we will assume that any solution $\mathbf{y}$ is associated with
the bipartite graph $H_{\mathbf{y}}=(V,T,E_{\mathbf{y}})$, where the nodes on
the one side correspond to individuals, the nodes on the other side to tasks
and there is an edge $e(v,t)$ for every pair $(v,t)$ with $v\in V$ and $t\in
T$ if and only if $y_{vt}\in(0,1)$, i.e., $y_{vt}$ is fractional.

Let $\mathbf{y}$ be a current solution of the program and $H_{\mathbf{y}}$ the
corresponding bipartite graph. If $H_{\mathbf{y}}$ contains cycles, then set
$C$ to be this cycle. Otherwise, set $C$ to be a path whose endpoints have
degree 1. Since $H_{\mathbf{y}}$ is bipartite, in both cases $C$ may be
uniquely expressed as the union of two matchings $M_{1}$ and $M_{2}$. Suppose
we increase all components of $\mathbf{y}$ corresponding to edges in $M_{1}$,
while decreasing all components corresponding to edges in $M_{2}$ until some
component reaches an integral value. Denote this solution by $\mathbf{y}_{1}$.
Symmetrically, by decreasing the values of the variables corresponding to
$M_{1}$ and increasing those corresponding to $M_{2}$, we get solution
$\mathbf{y}_{2}$. We choose the best of these two solutions by calculating
$F(\mathbf{y}_{1})$ and $F(\mathbf{y}_{2})$. We repeat the procedure until all
variables are integral.

Observe that each iteration requires evaluating the objective function $F$
twice. This is a significant drawback of this algorithm, especially for large
graphs, where the computation of the function is expensive. In the next
section we present a randomized version of pipage rounding that overcomes this
problem.

Approximation guarantees: Following the analysis of Ageev et al. (Ageev and
Sviridenko, 2004) we can show that Pipage is an $1/2$-approximation algorithm
for the TFC problem. Thus we have:

###### Theorem 2 ((Ageev and Sviridenko, 2004)).

The Pipage algorithm is an $\frac{1}{2}$-approximation algorithm for the TFC
problem.

For completeness we present this proof in Appendix A.1

Running time: The overall complexity of Pipage consists of the running time of
a gradient-ascent algorithm that finds a fractional solution
$\mathbf{y}^{\ast}$ to the Relaxed-TFC problem plus the running time of pipage
rounding. The latter is
$O\left(\left(\mathcal{T}_{F}+|V|+|T|\right)|E_{\mathbf{y}^{\ast}}|\right)$,
where $\mathcal{T}_{F}$ is the time required to evaluate the function $F$ and
$E_{\mathbf{y}^{\ast}}$ is the number of fractional components of the initial
solution $\mathbf{y}^{\ast}$. This is because each of the
$E_{\mathbf{y}^{\ast}}$ steps of pipage rounding requires time
$O\left(\mathcal{T}_{F}+|V|+|T|\right)$ since we run a Depth-First-Search and
two evaluations of $F$.

###  4.2. Randomized $\frac{3}{4}$ \- approximation algorithm

Here, we present a $\frac{3}{4}$-approximation algorithm for TFC. We call this
algorithm RPipage, because we use the randomized pipage rounding in order to
instantiate the Relax-Round algorithm.

The $L_{2}$ concave relaxation:

$L_{2}(\mathbf{x})=\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}-w(E_{G})+\sum_{(u,v)\in E_{G}}\sum_{t\in
T}w_{uv}\min(1,x_{ut}+x_{vt}).$

For $L_{2}$ we have the following:

###### Proposition 0.

$L_{2}$ satisfies Properties 1 and 2.

The proof of Proposition 3 is given in Appendix A.2.

Randomized pipage rounding Here, we briefly present the randomized pipage
scheme originally proposed by Gandhi (Gandhi et al., 2002). Randomized pipage
rounding proceeds in iterations, just like (deterministic) pipage rounding. If
$\mathbf{y}$ is the current fractional solution of the rounding algorithm, we
calculate $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ (same as in pipage rounding)
and then we probabilistically set $y^{\prime}$ equal to either
$\mathbf{y}_{1}$ or $\mathbf{y}_{2}$. For more details we refer the reader to
Appendix C.2.

Approximation guarantees: In order to prove the $\frac{3}{4}$-approximation
ratio of RPipage for TFC we need the following Lemma:

###### Lemma 0 ((Chekuri et al., 2010)).

If we use $\Xi$ to denote the randomized pipage algorithm that rounds a
fractional solution $\mathbf{y}$ to an integral solution $\mathbf{x}$, i.e.
$\Xi(\mathbf{y})=\mathbf{x}$, then $\Xi$ satisfies the following properties:

  * •

$\mathbb{E}_{\Xi}[\mathbf{x}]=\mathbf{y}$

  * •

$\mathbb{E}_{\Xi}[(1-x_{ut})(1-x_{vt})]\leq(1-y_{ut})(1-y_{vt})$, for all
$u,v\in V$ and $t\in T$

The proof of this lemma is due to Chekuri et al. (Chekuri et al., 2010), and
thus omitted. The most important consequence of Lemma 4 is the following
proposition, the proof of which is given in Appendix A.3

###### Proposition 0.

Under Assumption 1, for all $\mathbf{x},\mathbf{y}$ such that
$\mathbf{x}=\Xi(\mathbf{y})$ and $\Xi$ being the randomized pipage rounding,
we have that:

$\mathbb{E}_{\Xi}[L(\mathbf{x})]\geq\frac{3}{4}L(\mathbf{y})$

Now, let $\mathbf{y}^{\ast}$ be the optimal fractional solution of the
Relaxed-TFC problem with objective $L_{2}$ and
$\Xi(\mathbf{y}^{\ast})=\mathbf{x}^{\ast}$, with $\Xi$ being the randomized
pipage rounding scheme. Also, let $\mathbf{x}_{\text{int}}$ be the optimal
solution of the integral problem TFC. Then, it holds that:

$F(\mathbf{x}^{\ast})=L_{2}(\mathbf{x}^{\ast})\geq\frac{3}{4}L_{2}(\mathbf{y}^{\ast})\geq\frac{3}{4}F(\mathbf{x}_{\text{int}}).$

Thus, we have the following theorem:

###### Theorem 6.

Under Assumption 1, RPipage is a $\frac{3}{4}$-randomized approximation
algorithm for the TFC problem.

Running time: The overall complexity of RPipage consists of the running time
of a gradient-ascent algorithm that finds a fractional solution
$\mathbf{y}^{\ast}$ to the Relaxed-TFC problem with objective $L_{2}$ plus the
running time of the randomized pipage rounding scheme, which is
$O((|T|+|V|)|T||V|)$; assuming that the number of tasks $|T|<|V|$, this
becomes $O(|T||V|^{2})$. In contrast to deterministic pipage rounding, observe
that randomized pipage rounding does not require evaluating the objective
function. This results in a significant computational speed-up.

Discussion: In the future, it would be interesting to examine if _swap
rounding_ (Chekuri et al., 2010), can be used in place of randomized pipage
rounding and whether such a scheme can lead to more efficient algorithms. We
leave this as an open problem.

###  4.3. Tuning the hyperparameter $\lambda$

In order for Theorem 6 to hold, we need to make the following assumption:

###### Assumption 1.

(Balancing Assumption) Consider a feasible fractional solution $\mathbf{y}$.
We assume that the following holds:

$\displaystyle\lambda\sum_{v\in V}\sum_{t\in T}c_{vt}y_{vt}-w(E_{G})\geq 0$
$\displaystyle\lambda\geq\frac{w(E_{G})}{\sum_{v\in V}\sum_{t\in
T}c_{vt}y_{vt}},$

where $w(E_{G})=\sum_{(u,v)\in E_{G}}w_{uv}$. If we also assume that $0\leq
c_{vt}\leq 1$ for all $v\in V$ and $t\in T$, then we have

$\displaystyle\lambda\geq\frac{w(E_{G})}{|V|}=\frac{d_{\text{avg}}}{2},$

where $d_{\text{avg}}$ is the average degree of the nodes in the conflict
graph $G$ and we used the fact that $\sum_{t\in T}y_{vt}=1,\forall v\in V$.

The above assumption provides a way to tune the balancing parameter $\lambda$.
In practice, we do the following: we introduce the _balancing factor_
$\alpha\in\mathbb{R}_{>0}$ and we set $\lambda$ to be
$\lambda=\alpha\times\frac{d_{\text{avg}}}{2}$. In practice, we tune $\alpha$
as follows: for different values of $\alpha$ we evaluate the task and the
social satisfaction terms $\left(F_{R}^{(\alpha)},F_{G}^{(\alpha)}\right)$.
Then, we pick the value of $\alpha$ that gives the desired balance between the
two terms.

##  5\. Computational speedups

We discuss here a few methods we use in order to speedup our algorithms. All
heuristics we discuss here can be applied to both Pipage as well as RPipage.

Converting convex to linear programs: The algorithms we developed in Section 4
are based on the fact that the Relaxed-TFC problem with objective functions
$L_{1}$ and $L_{2}$ is a concave problem with linear constraints and it can be
solved in polynomial time via an application of gradient ascent. In fact, we
show that there is a way to rewrite the Relaxed-TFC problems with objectives
$L_{1}$ and $L_{2}$ as linear programs, by adding some extra variables.

For the Relaxed-TFC problem with objective $L_{1}$, this can be done as
follows: first, we substitute the term $\min(1,\min_{t}(2-x_{ut}+x_{vt}))$
with the new variable $z_{uv}$ and the objective becomes:

$L_{1}(\mathbf{x})=\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}+\sum_{(u,v)\in E_{G}}w_{uv}z_{uv}.$

Then, we also add the constraints $z_{uv}\leq 1$ and $z_{uv}\leq
2-x_{ut}-x_{vt},t\in T$. The full linear program is given in Appendix A.4

The corresponding linearization of the $L_{2}$ objective can be done as
follows: we substitute the term $\min(1,x_{ut}+x_{vt})$ with a new variable
$x_{uvt}$ such that:

$L_{2}(\mathbf{x})=\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}-w(E_{G})+\sum_{(u,v)\in E_{G}}\sum_{t\in T}w_{uv}x_{uvt}.$

We also add the constraints $x_{uvt}\leq 1$ and $x_{uvt}\leq x_{ut}+x_{vt}$.
The complete linear program is given in Appendix A.5.

The advantage of converting the convex problems into linear is that solving a
linear program is much more efficient than solving a convex program with
linear constraints. In practice, using the Gurobi solver we obtained speedups
up to 500x (see Table 4).

Sparsification: When the task capacities are small and the conflict graph is
dense, a heuristic, we named Sparsify, that works well in practice is randomly
removing conflict edges. That is, we keep each conflict edge with a certain
probability $p$. Otherwise, with probability $(1-p)$ we discard the edge. This
greatly reduces the number of terms we need to evaluate $F_{G}$ in our
objective resulting in computational speedups when optimizing the fractional
relaxation.

Note that when $p=1$, we don’t alter the objective. As $p$ decreases, we
remove more conflict edges, resulting in computational speedups, although our
fractional solution might not be optimal. Selecting $p$ is problem specific. A
rule of thumb is that the denser the conflict graph, the lower we can set $p$.

Compact: Our intuition, but also our real-world datasets (see Section 1 and
Appendix D.2), reveal that our data have the following pattern: the complement
of the conflict graph, i.e., the friend graph, consists of relatively small
densely-connected communities with similar task preferences. Intuitively, for
two individuals $u,v$ that belong in the same community and have similar
preferences we would expect that the vectors of $x_{ut}$’s and $x_{vt}$’s will
be similar for all $t\in T$. Taking this to the extreme: individuals $u,v$
with the same neighbors in the conflict graph $G_{G}$ and the same preferences
for tasks in $T$ should have identical values $x_{ut}$, $x_{vt}$.

Formally, this is captured in the following theorem, which is proved in
Appendix A.6:

###### Theorem 1.

Consider two individuals $u,v\in V$ which have identical neighbors in $G_{G}$
(i.e.,$(u,w)\in E_{G}\Leftrightarrow(v,w)\in E_{G}$) and have identical
project preferences (i.e., $c_{ut}=c_{vt},\forall t\in T$). Then, there exists
an optimal solution $\mathbf{y}$ of Relaxed-TFC such that
$x_{ut}=x_{vt},\forall t\in T$.

Motivated by the above theorem we define the Compact algorithm. On a high-
level the idea is to compact densely-connected subgraphs into supernodes. Note
that the supernodes need not be nodes that have identical neighborhood in $G$;
after all, it may be unreasonable to assume that this will happen in practice.
However, using a graph-partitioning algorithm (e.g., spectral clustering (Von
Luxburg, 2007), finding dense components (Charikar, 2000)) we can partition
the original set of nodes into supernodes with similar neighborhoods. Let $S$
be the set of supernodes, which is a partition of the original set of nodes
$V$. Then, we create a conflict graph between supernodes; the number of
conflict edges between two supernodes $A$ and $B$ is approximately
$|A|\times|B|$ (almost every node of $A$ is in conflict with every node of
$B$). Thus, we set in this new conflict graph we set the weight of edge
$(A,B)$ to be $w_{AB}=|A|\times|B|$ (assuming that each edge of the original
graph has unit weight). The next step is to solve the following _compact_
Relaxed-TFC problem:

(10) max $\displaystyle L(\mathbf{x})$ (11) s.t. $\displaystyle\sum_{t\in
T}x_{vt}=1,\forall v\in S$ (12) $\displaystyle\sum_{v\in S}|v|x_{vt}\leq
p_{t},\forall t\in T$ (13) $\displaystyle 0\leq x_{vt}\leq 1,\forall v\in
S,\forall t\in T.$

where we use $|v|$ to denote the number of simple nodes in the supernode $v$.

Then, we unroll the solution to obtain a fractional solution for the original
graph. That is, for each $v\in V$ we set $x_{vt}=x_{St}$, where $S$ is the
supernode $v$ belongs to. Finally, we round the fractional solution to obtain
an integral solution. Depending on whether we use $L_{1}$ or $L_{2}$ as our
objective, we then round the fractional solution using Pipage or RPipage
respectively.

##  6\. Experiments

In this section, we evaluate our framework using both real-world as well as
synthetic datasets. The experiments prove the effectiveness and efficiency of
our algorithms as well as the versatility of our model to encompass many
different real-world scenarios involving assignment problems with conflicts.
We make the code and the data we used in our experiments publicly available at
https://github.com/jasonNikolaou/TF-Conflicts.git

###  6.1. Baselines and Setup

Baselines: For our experiments we use the following baselines:

_Quadratic :_ This is the optimal algorithm, i.e., the algorithm that solves
the original TFC problem as expressed in Equations (1)-(4). We use an off-the
shelf solver to implement Quadratic, but even though this is a powerful
solver, we can run Quadratic only for small datasets since the solver is asked
to optimize a non-convex quadratic function subject to integral constraints.

_Greedy :_ The Greedy algorithm sequentially assigns an individual to the best
team (i.e., the team that maximizes the objective function $F$) given that the
constraints are satisfied. The algorithm terminates when all individuals are
assigned. We refer the reader to Appendix B for a detailed analysis of Greedy.

_Random :_ This is an algorithm that randomly assigns each individual to a
team until all individuals are assigned.

_Manual :_ This is the _manual_ assignment of individuals to tasks as made by
a human expert, which is available only in some datasets.

Experimental setup: Our experimental setup is descried in Appendix D.1. Unless
otherwise stated we use the “linearization” speedup presented in Section 5.

###  6.2. Datasets

For our experiments, we use three different types of data: (a) data of
preferences of students with respect to projects and collaborators in
educational settings, (b) data from the Bureau of Labor statistics that
concern employees and their assignment to company departments and, finally,
(c) a synthetic dataset that we use to test the scalability of our algorithms
and the speedups described in Section 5. We describe these datasets below. A
summary of the characteristics of each dataset is shown in Table 1.

Table 1. Number of nodes $|V|$, tasks $|T|$ and conflict edges $|E|$ for each dataset. Dataset | $|V|$ | $|T|$ | $|E|$
---|---|---|---
Class-B | 28 | 7 | 359
Class-C | 26 | 6 | 311
Class-A | 168 | 14 | 13952
Class-D | 37 | 8 | 648
Company | 4000 | 4 | 10166
Synth-TF | 1000 | 10 | 450454

Education data: This is data coming from courses in a US institution 222IRB
exception was obtained in order to use an anonymized version of the data.. In
the classes we considered, there were a number of projects (with fixed
capacities) available to students and each student filled in a form with their
project preferences (each student ranked the projects from best to worst) and
their preferences with respect to other students they want to work with in the
same project. We have data from four such classes: Class-A, Class-B, Class-C
and Class-D. These datasets do not contain a conflict graph between students,
but instead a _friend_ graph (indicative such graphs are shown in Appendix
D.2), i.e. two students that have an edge between them are friends and want to
work together. We define the conflict graph as the complement of the friend
graph. We assign unit weight to each edge of the conflict graph.

Next, we have to construct the preference graph by assigning weight $c_{u,p}$
for each student $u$ and project $t$. Let $rank_{u}(t)\in[|T|]$ be the rank of
project $t$ in student’s $u$ preference list (1 is the best, $|T|$ is the
worst). We considered the following functions:

  * $\bullet$

inverse (Inverse): $c_{u,t}=\frac{1}{\text{rank}_{u}(t)}$

  * $\bullet$

linear-normalized (LinNorm): $c_{u,t}=\frac{|T|-\text{rank}_{u}(t)+1}{|T|}$

Employee data: Based on statistics from the _U.S. Bureau of Labor Statistics_
333bls.gov/cps/cpsaat11.htm for 2022, we built a dataset of employees in an
company. Specifically, we created a company with 4000 employees and four
departments: IT, Sales, HR, PR. Each department has 1000 employees. IT and
Sales departments are male dominated while HR and PR are female dominated. The
distribution of males and females in each department are according to the data
in the _Management occupations_ section of the _U.S. Bureau of Labor
Statistics_. In our experiments, we add conflict edges between all male
employees, since our objective is to distribute the male employees more
evenly. Equivalently, we could have added conflict edges between all females.
Generally, depending on the diversity goal, one can add conflicts judiciously
to guide the diversification process. For employee preferences, we set
$c_{ut}=1$, if $t$ is the original department of $u$, otherwise $c_{ut}=0$. We
assume that with probability $1\%$ an employee is suitable for switching to a
new department. For those employees we set $c_{ut}=1$, where $t$ is the
department to which employee $u$ may switch.

Synthetic data: We also created a synthetic dataset (Synth-TF) to test the
speedups we discussed in Section 5. For this we created $|V|=1000$
individuals. The conflict graph is defined as the complement of the following
friend graph: the friend graph is a planted partition graph where each
partition has $100$ nodes connected with probability $0.99$. Edges across
partitions are added with probability $10^{-5}$. For each partition we select
a primary project $t$ and set $c_{vt}=1$ for all nodes $v$ in the partition.
Next, for each node $v$ we choose uniformly at random a project $t^{\prime}$
and set $c_{vt^{\prime}}=1$.

###  6.3. Forming teams in education settings

In this section, we evaluate the quantitative and qualitative performance of
our algorithms using the education datasets.

Figure 1. Education data; approximation ratio of the different algorithms. For
all datasets we used the Inverse project-preference function and $\alpha=10$.

Approximation ratios

Quantitative performance of our algorithms: We evaluate the qualitative
performance of our algorithms using the _approximation ratio_ AR, i.e. the
ratio of the objective function evaluated at the solution and the optimal
value.

Figure 1 shows the approximation ratios achieved by our algorithms and the
different baselines. For all datasets we used the LinNorm project preference
function. The results for the Inverse preference function are presented in
Appendix D.3). The results demonstrate that our algorithms have approximation
ratio very close to $1$.

Interestingly, and despite the fact that in Appendix B we show that the worst-
case approximation ratio of Greedy is unbounded, in practice Greedy has AR
score very close to $1$. We conjecture that this is true due to the
correlation between students’ friendships and preferences. In fact, we believe
that one can bound the approximation ratio of Greedy under such correlation
patterns; we leave this as future work.

Somewhat surprisingly, the performance of Random is quite good, although not
comparable to the other algorithms. This can be explained by the high density
of the conflict graph (or the sparseness of the friend graph) and the fact
that the capacities of projects are small relative to the number of
individuals. Since the conflict graph is almost a complete graph, small random
teams inevitably have large number of conflict edges between them. That said,
our analysis demonstrates that the solution given by Random has poor
qualitative characteristics.

For these experiments we used $\alpha=10$ for all datasets, since our primary
goal was to assign students to projects they like. Assigning students with
their friends was a secondary objective according to the course instructors.
We chose the value of $\alpha$ following the grid-search procedure of Section
4.3; the details are given in Appendix D.4. Note that by our selection of
$\alpha$, the balancing assumption holds and thus the approximation guarantees
of RPipage hold.

Qualitative performance of our algorithms: In applications such as the
assignment of students to teams, what matters is not just the value of the
objective function, but the per-student satisfaction. In this section, we
analyze the solutions provided by our algorithms and our baselines and compare
those with the _manual_ solution provided by a domain expert who tries to find
an empirically good assignment based on the input data.

In order to evaluate the quality of the results, we compute the following
metrics. Given a solution $\mathbf{x}$ to our problem we define
$r(v,\mathbf{x})$ to be the $\text{rank}_{v}(t)$, where $x_{vt}=1$, i.e.
$r(v,\mathbf{x})$ is the rank – according to $v$ – of the task to which $v$
was assigned. Then, we define the $\mathcal{M}$-preference metric to be:

$\mathcal{M}Q_{R}(\mathbf{x})=\mathcal{M}(r(v,\mathbf{x})\mid v\in V).$

In the above equation, $\mathcal{M}$ can be substituted by $\max$ or avg and
the preference metric corresponds to the maximum and average ranking of the
projects assigned to students; note that the minimum is not used as it is
identical across algorithms and does not provide any insight. Intuitively, the
lower the value of $\mathcal{M}Q_{R}(\mathbf{x}_{\mathcal{A}})$ for a solution
provided by an algorithm $\mathcal{A}$, the better the algorithm.

Similarly, we define $\mathcal{M}Q_{G}(\mathbf{x})$ to be the $\max$ or avg
number of friends (non-conflicts) assigned to students in $v$. In this case,
the larger the value $\mathcal{M}Q_{G}(\mathbf{x}_{\mathcal{A}})$ for a
solution provided by an algorithm $\mathcal{A}$, the better the algorithm.

Table 2. Education data; $\mathcal{M}Q_{R}(\mathbf{x}_{\mathcal{A}})$ for $\mathcal{M}=\\{\textit{max},\textit{avg}\\}$ of assigned project preferences and $\mathcal{A}$ being all algorithms; we also report std \- the standard deviation for $\textit{avg}Q_{R}$; Inverse project preference function and $\alpha=10$. Dataset | Algorithm | $\textit{max}Q_{R}$ | $\textit{avg}Q_{R}$ | std
---|---|---|---|---
Class-A | Quadratic | 14.0 | 1.80 | 2.45
Pipage | 14.0 | 1.82 | 2.51
RPipage | 14.0 | 1.81 | 2.50
Greedy | 14.0 | 1.95 | 2.50
Random | 14.0 | 9.09 | 4.29
Manual | 14.0 | 2.79 | 2.44
Class-B | Quadratic | 4.0 | 1.57 | 0.90
Pipage | 4.0 | 1.57 | 0.90
RPipage | 4.0 | 1.57 | 0.90
Greedy | 7.0 | 2.18 | 1.79
Random | 9.0 | 4.75 | 2.76
Manual | 3.0 | 1.71 | 0.80
Class-C | Quadratic | 6.0 | 1.62 | 1.15
Pipage | 6.0 | 1.62 | 1.15
RPipage | 6.0 | 1.62 | 1.15
Greedy | 6.0 | 2.12 | 1.48
Random | 6.0 | 3.42 | 1.67
Manual | 6.0 | 2.04 | 1.09
Class-D | Quadratic | 2.0 | 1.05 | 0.23
Pipage | 2.0 | 1.06 | 0.23
RPipage | 2.0 | 1.06 | 0.23
Greedy | 2.0 | 1.05 | 0.23
Random | 8.0 | 4.45 | 2.29
Table 3. Education data; $\mathcal{M}Q_{G}(\mathbf{x}_{\mathcal{A}})$ for $\mathcal{M}=\\{\textit{max},\textit{avg}\\}$ of number of friends per student and $\mathcal{A}$ being all algorithms; we also report std \- the standard deviation for $\textit{avg}Q_{G}$; Inverse project preference function and $\alpha=10$. Dataset | Algorithm | ${\max}Q_{G}$ | $\textit{avg}Q_{G}$ | std
---|---|---|---|---
Class-A | Quadratic | 4 | 0.65 | 0.78
Pipage | 2 | 0.1 | 0.34
RPipage | 1 | 0.08 | 0.26
Greedy | 3 | 0.65 | 0.74
Random | 1 | 0.4 | 0.49
Manual | 3 | 0.63 | 0.63
Class-B | Quadratic | 2 | 0.64 | 0.77
Pipage | 2 | 0.64 | 0.77
RPipage | 2 | 0.57 | 0.78
Greedy | 3 | 0.79 | 1.08
Random | 2 | 1.5 | 0.87
Manual | 2 | 0.64 | 0.67
Class-C | Quadratic | 2 | 0.54 | 0.57
Pipage | 1 | 0.38 | 0.49
RPipage | 1 | 0.38 | 0.49
Greedy | 2 | 0.69 | 0.67
Random | 1 | 0.54 | 0.5
Manual | 2 | 0.69 | 0.54
Class-D | Quadratic | 3 | 0.43 | 0.72
Pipage | 1 | 0.29 | 0.45
RPipage | 1 | 0.23 | 0.42
Greedy | 2 | 0.38 | 0.54
Random | 0 | 0.0 | 0.0

Table 2 shows that students got a better project on average when using the
Quadratic, Pipage and RPipage algorithms compared to the Manual assignment.
Table 5 shows that students got the same (or almost the same) average number
of friends using the Quadratic, Pipage and RPipage algorithms as in the manual
assignment.

###  6.4. Forming teams of employees

In this section, we use the Company dataset in order to evaluate our
algorithms’ ability to form diverse teams of employees.

Figure 2. Employee data; approximation ratio of the different algorithms for
$\alpha=1,2,3,4$.

Approximation ratios

Quantitative performance of our algorithms: Figure 2 shows the approximation
ratios of our algorithms and baselines for the Company dataset and for
$\alpha=1,2,3,4$. Somewhat surprisingly, for $\alpha=1$ our algorithms have a
approximation ratio close to $0.8$, while Greedy is almost optimal. Random has
significantly lower approximation ratio than the other algorithms; most of the
times less than $0.5$. In general, all other algorithms have approximation
ratio close to $1$. It is interesting to observe that in this dataset Greedy
performs almost optimally for all choices of $\alpha$; despite the fact that
its worst case approximation factor is unbounded (see Appendix B). As we
discussed before, we believe that the reason for this is the correlation
between conflicts and task preferences.

Figure 3. Employee data; Diversity per department before (1${}^{\text{st}}$
row) and after (2${}^{\text{nd}}$ row) we run the Quadratic algorithm
($\alpha=2$). $8\%$ of the employees changed department. The average male-
female percentage gap decreased from $35\%$ to $26\%$.

Percentage of male vs female employees per department before and after we run
our algorithm.

Qualitative performance of our algorithms: In this dataset, we evaluate the
qualitative performance of our framework by showing how the optimal solution
to our problem (obtained by Quadratic), affected the diversification of the
teams. Figure 3 demonstrates exactly this. While only $8\%$ of the employees
changed department, the average male-female percentage gap decreased from
$35\%$ to $26\%$. Varying the value of $\alpha$ we can control this balance.
Specifically, if we decrease the value of $\alpha$ the number of people who
change department increases, while the average male-female gap decreases.
Hyperparameter tuning for the Company dataset is further discussed in Appendix
D.7.

###  6.5. Evaluating the speedup techniques

In this section, we use the Synth-TF dataset to demonstrate the speedups
obtained by the different techniques we discussed in Section 5. As we
discussed, solving the TFC problem as described in Equations (5)-(8) using a
convex solver does not scale up. Thus, we apply to this original problem
sparsification and then run the convex solver; we call this algorithm
Sparsify-Concave. For the Sparsify algorithm we used $p=0.01$, i.e., we kept
only $1\%$ of the edges of the conflict graph. Alternatively, we transform the
problem into a problem with a linear objective by adding auxiliary variables
and constraints (as discussed in Section 5) and run the RPipage algorithm. We
call this algorithm Linear. Another algorithm we use is Sparsify-Linear, which
combines sparsification and linearization. Finally, we also combine Compact
with Linear to obtain the Compact-Linear algorithm. Note that for the
implementation of Compact we use the spectral clustering algorithm ((Von
Luxburg, 2007)) available in scikit-learn 444scikit-
learn.org/stable/modules/generated/sklearn.cluster.SpectralClustering.html.

Figure 4 shows the approximation ratios of the above heuristics and Table 4
the running times of the same heuristics on the Synth-TF dataset. For this
experiment, we set the value of $\alpha=10$.

Although all algorithms perform almost optimally, speed-ups vary. First,
trying to directly optimize the Concave relaxation results in a time-out of
our solver. Using Sparsify before optimizing the Concave relaxation renders
the problem solvable in $1000$ seconds. Using the Linear algorithm yields an
extra 3x speedup. Finally, combining Linear with either Sparsify or Compact
further reduces the running time down to $2-3$ seconds which is a 100x
speedup. In total, we managed to reduce the time from $1095$ seconds using
Sparsify-Concave to $2-3$ seconds combining Linear with one of Sparsify or
Compact.

Figure 4. Synth-TF dataset; approximation ratios of the speedups; We used
$\alpha=10$.

Approximation ratios of heuristics

Table 4. Running time (seconds) for the speed-ups Algorithm | Time (seconds)
---|---
Concave | time out
Sparsify-Concave | 1095
Linear | 342
Sparsify-Linear | 2
Compact-Linear | 3

##  7\. Conclusions

Motivated by the need to form teams of students in large project-based classes
we defined the TFC problem and showed that (a) it is NP-hard and that (b) it
is closely related to Max-$k$-Cut with given part sizes (Ageev and Sviridenko,
2004). For TFC, we designed a new efficient randomized approximation algorithm
and practical methods for speeding it up. We applied our algorithms to real-
world datasets and demonstrated their efficacy across different dimensions. In
the future, we want to further explore possible speedups for our algorithm and
also formally investigate the extremely good performance of Greedy in practice
– despite its unbounded worst-case approximation ratio.

Acknowledgements This research was supported by NSF grants 1813406 and
1908510. Evimaria Terzi was also supported by a grant from Max Planck
Institute for Software Systems (MPI-SWS).

## References

  * (1)
  * Ageev and Sviridenko (2004) Alexander A Ageev and Maxim I Sviridenko. 2004.  Pipage rounding: A new method of constructing algorithms with proven performance guarantee.  _Journal of Combinatorial Optimization_ 8 (2004), 307–328.
  * Anagnostopoulos et al. (2010) Aris Anagnostopoulos, Luca Becchetti, Carlos Castillo, Aristides Gionis, and Stefano Leonardi. 2010.  Power in unity: forming teams in large-scale community systems. In _Proceedings of the 19th ACM international conference on Information and knowledge management_. 599–608.
  * Anagnostopoulos et al. (2018) Aris Anagnostopoulos, Carlos Castillo, Adriano Fazzone, Stefano Leonardi, and Evimaria Terzi. 2018.  Algorithms for hiring and outsourcing in the online labor market. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1109–1118.
  * Andrews et al. (2011) Matthew Andrews, Mohammad Taghi Hajiaghayi, Howard Karloff, and Ankur Moitra. 2011.  Capacitated metric labeling. In _Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 976–995.
  * Boyd and Vandenberghe (2004) Stephen P Boyd and Lieven Vandenberghe. 2004.  _Convex optimization_.  Cambridge university press.
  * Charikar (2000) Moses Charikar. 2000.  Greedy approximation algorithms for finding dense components in a graph. In _International workshop on approximation algorithms for combinatorial optimization_. Springer, 84–95.
  * Chekuri et al. (2010) Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. 2010.  Dependent randomized rounding via exchange properties of combinatorial structures. In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_. IEEE, 575–584.
  * Gale and Shapley (1962) David Gale and Lloyd S Shapley. 1962.  College admissions and the stability of marriage.  _The American Mathematical Monthly_ 69, 1 (1962), 9–15.
  * Gandhi et al. (2002) Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. 2002.  Dependent rounding in bipartite graphs. In _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings._ IEEE, 323–332.
  * Goemans and Williamson (1994) Michel X Goemans and David P Williamson. 1994.  New 34-approximation algorithms for the maximum satisfiability problem.  _SIAM Journal on Discrete Mathematics_ 7, 4 (1994), 656–666.
  * Gusfield and Irving (1989) Dan Gusfield and Robert W Irving. 1989.  _The stable marriage problem: structure and algorithms_.  MIT press.
  * Kargar et al. (2013) Mehdi Kargar, Morteza Zihayat, and Aijun An. 2013.  Finding affordable and collaborative teams from a network of experts. In _Proceedings of the 2013 SIAM international conference on data mining_. SIAM, 587–595.
  * Karp (2010) Richard M Karp. 2010.  _Reducibility among combinatorial problems_.  Springer.
  * Kleinberg and Tardos (2002) Jon Kleinberg and Eva Tardos. 2002.  Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields.  _Journal of the ACM (JACM)_ 49, 5 (2002), 616–639.
  * Kuhn (1955) Harold W Kuhn. 1955.  The Hungarian method for the assignment problem.  _Naval research logistics quarterly_ 2, 1-2 (1955), 83–97.
  * Lappas et al. (2009) Theodoros Lappas, Kun Liu, and Evimaria Terzi. 2009.  Finding a team of experts in social networks. In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_. 467–476.
  * Majumder et al. (2012) Anirban Majumder, Samik Datta, and KVM Naidu. 2012.  Capacitated team formation problem on social networks. In _Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining_. 1005–1013.
  * McVitie and Wilson (1971) David G McVitie and Leslie B Wilson. 1971.  The stable marriage problem.  _Commun. ACM_ 14, 7 (1971), 486–490.
  * Negreiros and Palhano (2006) Marcos Negreiros and Augusto Palhano. 2006.  The capacitated centred clustering problem.  _Computers & operations research_ 33, 6 (2006), 1639–1663.
  * Vombatkere and Terzi (2023) Karan Vombatkere and Evimaria Terzi. 2023.  Balancing Task Coverage and Expert Workload in Team Formation. In _Proceedings of the 2023 SIAM International Conference on Data Mining (SDM)_. SIAM, 640–648.
  * Von Luxburg (2007) Ulrike Von Luxburg. 2007.  A tutorial on spectral clustering.  _Statistics and computing_ 17 (2007), 395–416.
  * Zhu et al. (2010) Shunzhi Zhu, Dingding Wang, and Tao Li. 2010.  Data clustering with size constraints.  _Knowledge-Based Systems_ 23, 8 (2010), 883–889.

##  Appendix A Proofs

###  A.1. Proof of Theorem 2

We begin with the following lemma:

###### Lemma 0.

Let $\mathbf{y}$ be a (fractional) feasible solution to the TFC-1 problem.
Then, for every $u,v\in V$ we have:

$\displaystyle 1-\sum_{t\in
T}y_{uv}y_{vt}\geq\frac{1}{2}\min\left(1,\min_{t\in
T}(2-y_{uv}-y_{vt})\right)$

###### Proof.

Let $z_{uv}=\min\left(1,\min_{t}(2-y_{uv}-y_{vt})\right)$. Define

$t^{\prime}=\arg\max_{t\in T}(y_{ut}+y_{vt})$

and

(14) $\displaystyle q_{uv}=y_{ut^{\prime}}+y_{vt^{\prime}}.$

Then,

(15) $\displaystyle z_{uv}=\min(1,2-q_{uv}).$

Also, it holds that

(16) $\displaystyle\sum_{t\in T}y_{ut}+y_{vt}=\sum_{t\in T}y_{ut}+\sum_{t\in
T}y_{vt}=1+1=2$

as well as the arithmetic-geometric mean inequality which says that for any
two positive numbers $a,b$:

(17) $\displaystyle\left(\frac{a+b}{2}\right)^{2}\geq ab.$

Thus, we have:

$\displaystyle 1-\sum_{t\in T}y_{ut}y_{vt}$
$\displaystyle=1-y_{ut^{\prime}}y_{vt^{\prime}}-\sum_{t\neq
t^{\prime}}y_{ut}y_{vt}$ $\displaystyle\geq
1-\left(\frac{y_{ut^{\prime}}+y_{vt^{\prime}}}{2}\right)^{2}-\sum_{t\neq
t^{\prime}}\left(\frac{y_{ut}+y_{vt}}{2}\right)^{2}$
$\displaystyle(\text{using }\eqref{ineq:arith-geom})$ $\displaystyle\geq
1-\left(\frac{q_{uv}}{2}\right)^{2}-\left(\frac{\sum_{t\neq
t^{\prime}}y_{ut}+y_{vt}}{2}\right)^{2}$ $\displaystyle(\eqref{def:q_uv}\text{
and convexity})$
$\displaystyle=1-\left(\frac{q_{uv}}{2}\right)^{2}-\left(\frac{2-(y_{ut^{\prime}}+y_{vt^{\prime}})}{2}\right)^{2}$
$\displaystyle(\text{using }\eqref{lemma:fact})$
$\displaystyle=1-\left(\frac{q_{uv}}{2}\right)^{2}-\left(1-\frac{q_{uv}}{2}\right)^{2}$
$\displaystyle(\text{using }\eqref{def:q_uv})$
$\displaystyle=q_{uv}-\frac{q_{uv}^{2}}{2}.$

_Case 1._ $1\leq q_{uv}\leq 2$. Then, by Eq. (15), $z_{uv}=2-q_{uv}$, and

(18) $\displaystyle 1-\sum_{t\in T}y_{ut}y_{vt}\geq
q_{uv}-\frac{q_{uv}^{2}}{2}\geq\frac{1}{2}z_{uv}.$

_Case 2._ $0\leq q_{uv}\leq 1$. Then, by Eq. (15), $z_{uv}=1$. By the
assumption of this case, for every $t$ it holds that

(19) $\displaystyle 0\leq y_{ut}+y_{vt}\leq 1.$

Using the arithmetic-geometric mean inequality (Eq. (17)), we have

$\displaystyle 1-\sum_{t\in T}y_{ut}y_{vt}$ $\displaystyle\geq 1-\sum_{t\in
T}\left(\frac{y_{ut}+y_{vt}}{2}\right)^{2}$
$\displaystyle=1-\frac{1}{4}\sum_{t\in T}(y_{ut}+y_{vt})^{2}$
$\displaystyle\geq 1-\frac{1}{4}\sum_{t\in T}(y_{ut}+y_{vt})$
$\displaystyle(\text{using }\eqref{lemma:fact})$
$\displaystyle=1-\frac{1}{4}2$ $\displaystyle=\frac{1}{2}z_{uv}$

∎

A corollary of Lemma 1 is the following:

###### Corollary 0.

If $\mathbf{y}$ is a (fractional) feasible solution to problem Relaxed-TFC
with objective $L_{1}$, then

$\displaystyle F(\mathbf{y})\geq\frac{1}{2}L_{1}(\mathbf{y}).$

Let $F^{\ast}$ be the value of the optimal (integral) solution to TFC. If
$\mathbf{y}^{\ast}$ is the optimal (fractional) solution to Relaxed-TFC with
objective $L_{1}$, it holds that $L_{1}(\mathbf{y}^{\ast})\geq F^{\ast}$. From
Corollary 2 we have that
$F(\mathbf{y}^{\ast})\geq\frac{1}{2}L_{1}(\mathbf{y}^{\ast})$. Using pipage
rounding we can round the fractional solution $\mathbf{y}^{\ast}$ to an
integral solution $\bar{\mathbf{x}}$ such that $F(\bar{\mathbf{x}})\geq
F(\mathbf{y}^{\ast})$. Thus,

$F(\bar{\mathbf{x}})\geq
F(\mathbf{y}^{\ast})\geq\frac{1}{2}L_{1}(\mathbf{y}^{\ast})\geq\frac{1}{2}F^{\ast}.$

$\epsilon$-convexity property. In order for $F(\bar{\mathbf{x}})\geq
F(\mathbf{y}^{*})$ to hold, the _$\epsilon$ -convexity_ property has to hold
(see (Ageev and Sviridenko, 2004)). Namely, the function
$\phi(\epsilon,\mathbf{y},R)=F(\mathbf{y}(\epsilon,R))$ has to be convex in
$\epsilon$ for every feasible solution $\mathbf{y}$ and for all paths and
cycles $R$ of the graph $H_{\mathbf{x}}$. We refer the reader to Section 4 in
(Ageev and Sviridenko, 2004) for a formal explanation. Note that in our
objective function except for the quadratic term, we also have a linear term.
However, the quadratic term dominates the linear term and $\phi(\epsilon)$
remains a quadratic polynomial with a non-negative leading coefficient.

###  A.2. Proof or Proposition 3

Property 1 To prove concavity it suffices to see that $L_{2}(\mathbf{x})$ is
the sum of concave functions. Note that $\min(1,x_{ut}+x_{vt})$ is concave.

Property 2: For the proof of Property 2, we need the following lemmas:

###### Lemma 0.

For all $x,y\in\\{0,1\\}$ it holds that

$\displaystyle 1-(1-x)(1-y)=x+y-xy=\min(1,x+y).$

The proof of this lemma consists of checking equality for all combinations of
integral values of $x$ and $y$.

###### Lemma 0 ((Goemans and Williamson, 1994)).

For all $x,y\in[0,1]$ it holds that

$1-(1-x)(1-y)\geq\frac{3}{4}\min(1,x+y).$

Now we are ready to prove the following:

###### Proposition 0.

For all integral $\mathbf{x}$ it holds that $F(\mathbf{x})=L_{2}(\mathbf{x})$.

###### Proof.

It holds that

$\displaystyle\sum_{(u,v)\in E}w_{uv}(1-\sum_{t\in T}x_{ut}x_{vt})=$
$\displaystyle w(E)-\sum_{(u,v)\in E}\sum_{t\in T}w_{uv}x_{ut}x_{vt}=$
$\displaystyle w(E)+\sum_{(u,v)\in E}\sum_{t\in T}w_{uv}\min(1,x_{ut}+x_{vt})$
$\displaystyle-\sum_{(u,v)\in E}\sum_{t\in T}w_{uv}(x_{ut}+x_{vt})=$
$\displaystyle w(E)+\sum_{(u,v)\in E}\sum_{t\in
T}w_{uv}\min(1,x_{ut}+x_{vt})-2w(E)=$ $\displaystyle\sum_{(u,v)\in
E}\sum_{t\in T}w_{uv}\min(1,x_{ut}+x_{vt})-w(E),$

where in the second equality we used lemma 3.

Using the above we have that

$\displaystyle F(\mathbf{x})$ $\displaystyle=\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}+\sum_{(u,v)\in E}w_{uv}(1-\sum_{t\in T}x_{ut}x_{vt})$
$\displaystyle=\sum_{(u,v)\in E}\sum_{t\in
T}w_{uv}\min(1,x_{ut}+x_{vt})+\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}-w(E)$ $\displaystyle=L_{2}(\mathbf{x}).$

∎

###  A.3. Proof of Proposition 5

###### Proof.

$\displaystyle\mathbb{E}_{\Xi}[L(\mathbf{x})]$
$\displaystyle=\mathbb{E}_{\Xi}[\sum_{(u,v)\in E}\sum_{t\in
T}w_{uv}\min(1,x_{ut}+x_{vt})$ $\displaystyle+\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}-w(E)]$ $\displaystyle=\mathbb{E}_{\Xi}[\sum_{(u,v)\in
E}\sum_{t\in T}w_{uv}(1-(1-x_{ut})(1-x_{vt}))$
$\displaystyle+\lambda\sum_{v\in V}\sum_{t\in T}c_{vt}x_{vt}-w(E)]$
$\displaystyle\geq\sum_{(u,v)\in E}\sum_{t\in
T}w_{uv}(1-(1-y_{ut})(1-y_{vt}))$ $\displaystyle+\lambda\sum_{v\in
V}\sum_{t\in T}c_{vt}y_{vt}-w(E)$ $\displaystyle\geq\frac{3}{4}\sum_{(u,v)\in
E}\sum_{t\in T}w_{uv}\min(1,y_{ut}+y_{vt})$
$\displaystyle+\frac{3}{4}\left(\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}y_{vt}-w(E)\right)$ $\displaystyle=\frac{3}{4}L(\mathbf{y})$

where in the second line we used Lemma 3, in the third line we used the
properties of the rounding operator, and in the fourth line we used Lemma 4
and Assumption 1. ∎

###  A.4. Linearization of $L_{1}$

(20) max $\displaystyle L_{1}(\mathbf{x})=\lambda\sum_{v\in V}\sum_{t\in
T}c_{vt}x_{vt}+\sum_{(u,v)\in E_{G}}w_{uv}z_{uv}$ (21) s.t.
$\displaystyle\sum_{t\in T}x_{vt}=1,\forall v\in V$ (22)
$\displaystyle\sum_{v\in V}x_{vt}\leq p_{t},\forall t\in T$ (23)
$\displaystyle z_{uv}\leq 1,\forall(u,v)\in E_{G},$ (24) $\displaystyle
z_{uv}\leq 2-x_{ut}-x_{vt},\forall(u,v)\in E_{G},t\in T.$

###  A.5. Linearization of $L_{2}$

(25) max $\displaystyle L_{2}(\mathbf{x})=\sum_{(u,v)\in E_{G}}\sum_{t\in
T}w_{uv}x_{uvt}+\lambda\sum_{v\in V}\sum_{t\in T}c_{vt}x_{vt}-w(E_{G})$ (26)
s.t. $\displaystyle\sum_{t\in T}x_{vt}=1,\forall v\in V$ (27)
$\displaystyle\sum_{v\in V}x_{vt}\leq p_{t},\forall t\in T$ (28)
$\displaystyle x_{uvt}\leq 1,\forall(u,v)\in E_{G},t\in T$ (29) $\displaystyle
x_{uvt}\leq x_{ut}+x_{vt},\forall(u,v)\in E_{G},t\in T.$

###  A.6. Proof of Theorem 1

###### Proof.

Let $\mathbf{y}$ be an optimal solution of the fractional relaxation of TFC
such that it does not hold that $y_{ut}=y_{vt},\forall t\in T$. Since
$\sum_{t}y_{ut}=\sum_{t}y_{vt}=1$, there exist $t_{1},t_{2}\in T$ such that
$y_{ut_{1}}\neq y_{vt_{1}}$ and $y_{ut_{2}}\neq y_{vt_{2}}$. Let
$\tilde{\mathbf{y}}$ be the ”symmetrical” solution where we have replaced $u$
with $v$ and vice versa. That is,

  * •

$\tilde{y}_{ut}=y_{vt},t\in T$

  * •

$\tilde{y}_{vt}=y_{ut},t\in T$

  * •

$\tilde{y}_{uv^{\prime}t}=y_{vv^{\prime}t},t\in T,(u,v^{\prime})\in E$

  * •

$\tilde{y}_{vv^{\prime}t}=y_{uv^{\prime}t},t\in T,(v,v^{\prime})\in E$

For the last two equalities note that since nodes $u$ and $v$ are
_symmetrical_ it holds that $(u,v^{\prime})\in
E\Leftrightarrow(v,v^{\prime})\in E$. Then,
$\mathbf{x}=(\mathbf{y}+\tilde{\mathbf{y}})/2$ is an optimal feasible solution
where $x_{ut}=x_{vt},\forall t\in T$. To see that note that the constraints
are linear and thus any convex combination of feasible solutions is also
feasible. Moreover, the objective function is linear and thus any convex
combination of optimal solutions is also optimal. Finally, concluding our
proof observe that

$\displaystyle x_{ut_{1}}=x_{vt_{1}}=\frac{y_{ut_{1}}+y_{vt_{1}}}{2}$

and

$\displaystyle x_{ut_{2}}=x_{vt_{2}}=\frac{y_{ut_{2}}+y_{vt_{2}}}{2}$

∎

##  Appendix B Analysis of the Greedy algorithm

Unbounded approximation ratio of Greedy: We have the following result in terms
of the performance of greedy with respect to our objective function:

###### Proposition 0.

Greedy has unbounded approximation ratio.

###### Proof.

Consider the following instance of our problem. $V=\\{u,v,z\\}$, with task
preferences $c_{ut_{1}}=1-\epsilon$, $c_{vt_{2}}=\epsilon$ and all other
preferences equal to 0. $T=\\{t_{1},t_{2}\\}$, with capacities $p_{t_{1}}=1$
and $p_{t_{2}}=2$. The conflict graph consists of the edge $(v,z)$ with weight
$w_{vz}=\mathcal{W}$. For the objective function assume that $\lambda=1$.
Running the Greedy yields the assignment: $u$ assigned to $t_{1}$ and $v,z$
are assigned to $t_{2}$. The optimal assignment is $z$ assigned to $t_{1}$ and
$u,v$ to $t_{2}$. The approximation ratio is:

$\text{AR}=\frac{(1-\epsilon)+\epsilon}{\mathcal{W}+\epsilon}\leq\frac{1}{\mathcal{W}}.$

As $\mathcal{W}\rightarrow\infty$, the approximation ratio
$\text{AR}\rightarrow 0$. ∎

Running time of Greedy: The complexity of Greedy is
$O(|V|^{2}|T|\mathcal{T}_{F})$, where $\mathcal{T}_{F}$ is the cost of
calculating $F$. We have $|V|$ iterations in total, since at each iteration we
assign one individual to a team. Each iteration costs $|V||T|\mathcal{T}_{F}$,
since we calculate the change in the objective function when considering the
addition of each remaining individual to each team which is not full.

##  Appendix C Dependent rounding schemes

###  C.1. Pipage rounding

In this section we give a description of the pipage rounding algorithm. For a
more detailed analysis we refer the reader to the original paper (Ageev and
Sviridenko, 2004). Pipage rounding is an iterative algorithm; at each
iteration the current fractional solution $\mathbf{y}$ is transformed into a
new solution $\mathbf{y}^{\prime}$ with smaller number of non-integral
components. Throughout, we will assume that any solution $\mathbf{y}$ is
associated with the bipartite graph $H_{\mathbf{y}}=(V,T,E_{\mathbf{y}})$,
where the nodes on the one side correspond to individuals, the nodes on the
other side to tasks and there is an edge $e(v,t)$ for every pair $(v,t)$ with
$v\in V$ and $t\in T$ if and only if $y_{vt}\in(0,1)$, i.e., $y_{vt}$ is
fractional.

Let $\mathbf{y}$ be a current solution satisfying the constraints of the
program and $H_{\mathbf{y}}$ the corresponding bipartite graph. If
$H_{\mathbf{y}}$ contains cycles, then set $C$ to be this cycle. Otherwise,
set $C$ to be a path whose endpoints have degree 1. Since $H_{\mathbf{y}}$ is
bipartite, in both bases $C$ may be uniquely expressed as the union of two
matchings $M_{1}$ and $M_{2}$. Given this, define a new solution
$\mathbf{y}(\epsilon,C)$ as follows:

  * $\bullet$

if $e\in E_{\mathbf{y}}\setminus C$, then $y_{e}(\epsilon,C)=y_{e}$.

  * $\bullet$

Otherwise, $y_{e}(\epsilon,C)=y_{e}+\epsilon,e\in M_{1}$ and
$y_{e}(\epsilon,C)=y_{e}-\epsilon,e\in M_{2}$.

For the above, set

$\epsilon_{1}=\min\\{\epsilon>0:(\exists e\in
M_{1}:y_{e}+\epsilon=1)\lor(\exists e\in M_{2}:y_{e}-\epsilon=0)\\}$

and

$\epsilon_{2}=\min\\{\epsilon>0:(\exists e\in
M_{1}:y_{e}-\epsilon=0)\lor(\exists e\in M_{2}:y_{e}+\epsilon=1)\\}.$

Let $\mathbf{y}_{1}=\mathbf{y}(-\epsilon_{1},C)$ and
$\mathbf{y}_{2}=\mathbf{y}(\epsilon_{2},C)$. Set
$\mathbf{y}^{\prime}=\mathbf{y}_{1}$, if
$F(\mathbf{y}_{1})>F(\mathbf{y}_{2})$, and
$\mathbf{y}^{\prime}=\mathbf{y}_{2}$ otherwise. Note that
$\mathbf{y}^{\prime}$ has smaller number of fractional components than
$\mathbf{y}$ and, thus, Pipage terminates after at most
$|E_{\mathbf{y}^{\ast}}|$ iterations, i.e., as many as the number of
fractional values in the $\mathbf{y}^{\ast}$ vector output by the optimization
algorithm. The following theorem states that $\mathbf{y}^{\prime}$ satisfies
the following constraints:

###### Theorem 1 ((Ageev and Sviridenko, 2004)).

Consider performing pipage roudning starting from the fractional solution
$\mathbf{y}$. Let $\mathbf{x}$ be the integral solution produced when Pipage
terminates. Then,

$\lfloor\sum_{e(v,t)\in\delta(v)}y_{vt}\rfloor\leq\sum_{e(v,t)\in\delta(v)}x_{vt}\leq\lfloor\sum_{e(v,t)\in\delta(v)}y_{vt}\rfloor+1,$

where for every $v\in V$ $\delta(v)$ is the set of edges in the preference
graph $R$, that are incident to $v$.

Since all $p_{t}$’s are integers (see Eq. 3), the above theorem implies that
$\mathbf{x}$ is a feasible solution.

###  C.2. Randomized pipage rounding

Here, we briefly present the randomized pipage scheme originally proposed by
Gandhi (Gandhi et al., 2002) adapted to our problem. Randomized pipage
rounding proceeds in iterations, just like (deterministic) pipage rounding. If
$\mathbf{y}$ is the fractional solution at the current iteration of the
rounding algorithm, we update $\mathbf{y}$ as follows:

If $e\in E_{\mathbf{y}}\setminus C$, then $y_{e}(\epsilon,C)=y_{e}$. If $e\in
C$, then $\mathbf{y}^{\prime}=\mathbf{y}_{1}$, with probability
$\epsilon_{2}/(\epsilon_{1}+\epsilon_{2})$. Otherwise, with probability
$\epsilon_{1}/(\epsilon_{1}+\epsilon_{2})$,
$\mathbf{y}^{\prime}=\mathbf{y}_{2}$. Note $C$, $\epsilon_{1}$,
$\epsilon_{2}$, $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ are the same as the ones
defined in the description of pipage rounding. As the number of fractional
elements of $\mathbf{y}$ decrease in every iteration, randomized pipage
rounding terminates after at most $O(|E_{\mathbf{y}^{\ast}}|)$ iterations,
where $\mathbf{y}^{\ast}$ is the solution to the Relaxed-TFC problem with
objective $L_{1}$.

##  Appendix D Experiments

###  D.1. Experimental setup

All of the experiments were run on a machine with an Intel(R) Xeon(R) Gold
6242 CPU @ 2.80GHz and 16GB memory. All of our code is written in Python
3.6.8. For linear and quadratic optimization we used Gurobi
555https://www.gurobi.com/. For optimizing concave functions we used CVXPY
666https://www.cvxpy.org/. In all our experiments, unless otherwise explicitly
stated, we use the “linearization” speedup we presented in Section 5.
Combining this with the Gurobi solver we obtain reasonable running times for
all our experiments. We also demonstrate the effect of this linearization in
Section 6.5. In fact, when we tried optimizing the concave relaxation with
linear constraints as expressed in Equations (5)-(9), our solver could not
terminate. For this concave problem we used CVXPY as Gurobi only solves linear
(and quadratic) problems. Our code will be made publicly available.

###  D.2. Indicative education datasets and their characteristics

Figures 5 and 6 show the friend graphs (i.e., the complement of the conflict
graphs) which is the input in the education datasets. Observe the sparsity of
both friend graphs.

Figure 5. Friend graph for dataset Class-B. On top of nodes are the anonymized
student ids.

Friend graph for a university course where students have provided their
friends, i.e. the people with whom they want to work together

Figure 6. Friend graph for dataset Class-A.

Friend graph for a university course where students have provided their
friends, i.e. the people with whom they want to work together

Figure 7 and figure 8 show the friend graph for Class-A and Class-B
respectively, where the nodes with the same color are assigned to the same
project.

Figure 7. Friend graph colored using the optimal team assignment (Quadratic)
for Class-A. Labels are omitted for clarity.

Friend graph for a university course where students have provided their
friends, i.e. the people with whom they want to work together. The nodes have
been colored according to their assignment to teams.

Figure 8. Friend graph colored using the optimal team assignment (Quadratic)
for Class-B. On top of nodes are the anonymized student ids.

Friend graph for a university course where students have provided their
friends, i.e. the people with whom they want to work together. The nodes have
been colored according to their assignment to teams.

###  D.3. Approximation ratios for LinNorm preference function

Figure 9 shows the approximation ratios for the LinNorm preference function.

Figure 9. Education data; approximation ratios for education datasets. For all
datasets we used the LinNorm project preference function and $\alpha=10$.

Approximation ratios for education datasets

###  D.4. Hyperparameter tuning for the education datasets

In Section 4.3, we gave a preview of how to tune the hyperparameter $\lambda$
or $\alpha$ by computing the terms
$\left(F_{G}^{\alpha},F_{R}^{\alpha}\right)$ for different values of $\alpha$.
This results in an ”elbow” plot that illustrates the trade-off between the two
terms and allows us to tune the hyperparameter in a informed way. We present
the plots for the LinNorm project preference function in Figure 10; the plots
for the Inverse project preference function are very similar and are presented
in Figure 11.

Note that when $\alpha=0$, the conflict term is almost equal to the number of
conflict edges, i.e. almost all individuals in conflict are placed in
different teams. When $\alpha=10$, the project preference term is almost equal
to the number of individuals, i.e. almost all individuals get their highest-
ranked project. This is because $c_{vt}=1$, if the highest-ranked project of
$v$ is $t$.

Figure 10. Education data; hyperparameter $\alpha$ tuning. We used the LinNorm
project preference function.

Hyperparameter tuning

Figure 11. Education data; hyperparameter $\alpha$ tuning. We used the Inverse
project preference function.

Hyperparameter tuning

###  D.5. Qualitative results for education datasets using the Inverse project
preference function

Table 5 shows that students got the same (or almost the same) average number
of friends using the Quadratic, Pipage and RPipage algorithms as in the Manual
assignment.

Table 5. Education data; $\mathcal{M}Q_{G}(\mathbf{x}_{\mathcal{A}})$ for $\mathcal{M}=\\{\textit{max},\textit{avg}\\}$ of number of friends per student and $\mathcal{A}$ being all algorithms; we also report std \- the standard deviation for $\textit{avg}Q$. For all datasets we used the Inverse project preference function and $\alpha=10$. Dataset | Algorithm | ${\max}Q_{G}$ | $\textit{avg}Q_{G}$ | std
---|---|---|---|---
Class-A | Quadratic | 4 | 0.65 | 0.78
Pipage | 2 | 0.1 | 0.34
RPipage | 1 | 0.08 | 0.26
Greedy | 3 | 0.65 | 0.74
Random | 1 | 0.4 | 0.49
Manual | 3 | 0.63 | 0.63
Class-B | Quadratic | 2 | 0.64 | 0.77
Pipage | 2 | 0.64 | 0.77
RPipage | 2 | 0.57 | 0.78
Greedy | 3 | 0.79 | 1.08
Random | 2 | 1.5 | 0.87
Manual | 2 | 0.64 | 0.67
Class-C | Quadratic | 2 | 0.54 | 0.57
Pipage | 1 | 0.38 | 0.49
RPipage | 1 | 0.38 | 0.49
Greedy | 2 | 0.69 | 0.67
Random | 1 | 0.54 | 0.5
Manual | 2 | 0.69 | 0.54
Class-D | Quadratic | 3 | 0.43 | 0.72
Pipage | 1 | 0.29 | 0.45
RPipage | 1 | 0.23 | 0.42
Greedy | 2 | 0.38 | 0.54
Random | 0 | 0.0 | 0.0

###  D.6. Qualitative results for education datasets using the LinNorm project
preference function

Tables 6 and 7 contain the qualitative results for the LinNorm project
preference function. Our algorithms are again comparable or better than the
baselines. An observation is that using the LinNorm project preference
function does not make a significance difference in the qualitative results.
Note again that our main focus on the education datasets was assigning
students to projects they like. Assigning them with friends was a secondary
goal.

Table 6. Education data; $\mathcal{M}Q_{R}(\mathbf{x}_{\mathcal{A}})$ for $\mathcal{M}=\textit{max},\textit{avg}$ of assigned project preferences and $\mathcal{A}$ being all algorithms; we also report std \- the standard deviation for $\textit{avg}Q_{R}$. For all datasets we used the LinNorm project preference function and $\alpha=10$. Dataset | Algorithm | ${\max}Q_{R}$ | $\textit{avg}Q_{R}$ | std
---|---|---|---|---
Class-A | Quadratic | 14.0 | 1.79 | 2.42
Pipage | 14.0 | 1.81 | 2.47
RPipage | 14.0 | 1.81 | 2.48
Greedy | 14.0 | 1.95 | 2.50
Random | 14.0 | 7.20 | 4.33
Manual | 14.0 | 2.79 | 2.44
Class-B | Quadratic | 4.0 | 1.57 | 0.86
Pipage | 4.0 | 1.57 | 0.90
RPipage | 4.0 | 1.57 | 0.90
Greedy | 7.0 | 2.18 | 1.79
Random | 7.0 | 4.36 | 2.24
Manual | 3.0 | 1.71 | 0.80
Class-C | Quadratic | 6.0 | 1.62 | 1.11
Pipage | 6.0 | 1.62 | 1.15
RPipage | 6.0 | 1.62 | 1.15
Greedy | 6.0 | 2.12 | 1.48
Random | 6.0 | 3.54 | 1.67
Manual | 6.0 | 2.04 | 1.09
Class-D | Quadratic | 1.875 | 1.05 | 0.20
Pipage | 1.875 | 1.05 | 0.20
RPipage | 1.875 | 1.05 | 0.20
Greedy | 1.875 | 1.05 | 0.20
Random | 7.125 | 4.17 | 1.92
Table 7. Education data; $\mathcal{M}Q_{G}(\mathbf{x}_{\mathcal{A}})$ for $\mathcal{M}=\\{\textit{max},\textit{avg}\\}$ of number of friends per student and $\mathcal{A}$ being all algorithms; we also report std \- the standard deviation for $\textit{avg}Q$. For all datasets we used the LinNorm project preference function and $\alpha=10$. Dataset | Algorithm | ${\max}Q_{G}$ | $\textit{avg}Q_{G}$ | std
---|---|---|---|---
Class-A | Quadratic | 3 | 0.71 | 0.79
Pipage | 2 | 0.15 | 0.37
RPipage | 1 | 0.10 | 0.30
Greedy | 3 | 0.65 | 0.74
Random | 0 | 0.00 | 0.00
Manual | 3 | 0.63 | 0.63
Class-B | Quadratic | 2 | 0.64 | 0.77
Pipage | 2 | 0.5 | 0.63
RPipage | 2 | 0.43 | 0.62
Greedy | 3 | 0.79 | 1.08
Random | 2 | 1.5 | 0.87
Manual | 2 | 0.64 | 0.67
Class-C | Quadratic | 1 | 0.54 | 0.50
Pipage | 1 | 0.38 | 0.49
RPipage | 1 | 0.46 | 0.50
Greedy | 2 | 0.69 | 0.67
Random | 1 | 0.46 | 0.50
Manual | 2 | 0.69 | 0.54
Class-D | Quadratic | 3 | 0.43 | 0.72
Pipage | 1 | 0.23 | 0.42
RPipage | 1 | 0.29 | 0.45
Greedy | 2 | 0.38 | 0.54
Random | 0 | 0.00 | 0.00

###  D.7. Hyperparameter tuning for the Company dataset

Figure 12. Employee data; Hyperparameter $\alpha$ tuning for the Company
dataset.

Hyperparameter tuning for the diversity dataset

Figure 13. Employee data; Controlling the balance between the fraction of
people who changed department PER and average gender gap per department AVG-
GAP using $\alpha$.

Hyperparameter tuning for the diversity dataset

Figure 13 shows the trade-off between the percentage of people who changed
department and the average percentage of the male-female gap per department.
Note that for values of $\alpha$ between $0.5$ and $2$ there is a plateau.
That is, the average gender gap per department remains almost constant
although more employees change department. After $\alpha$ drops below $0.5$
the average male-female gap drops significantly, but the percentage of people
who change departments grows very fast. According to the above plot a
reasonable choice for $\alpha$ is $\alpha=2$.

Figure 12 shows the trade-off between the task and social satisfaction terms.