A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

One way to solve a real-world problem is to formulate the problem as a mathematical optimization problem and find a solution with an optimization algorithm. However, it is not always easy to formulate an appropriate optimization problem as real-world problems often include intricate constraints and implicit preferences, which are usually simplified in order to solve optimization problems. Hence, an optimal solution obtained in this way is not guaranteed to be a “good solution” to the original real-world problem. To cope with this underlying inconsistency, the following two-stage approach would be promising: algorithms find multiple solutions and then users find what they like from these solutions. One may think that top-$k$ enumeration algorithms (see (Eppstein, 2008) for a survey) can be used for this purpose. However, this is not always the case since top-$k$ enumeration algorithms may output solutions similar to one another. (See (Wang et al., 2013; Yuan et al., 2016; Hao et al., 2020), for example). Such a set of solutions are not useful as a “catalog” of solutions provided to users.

As a way to solve this issue, algorithms are expected to find “diverse” solutions, and algorithms for finding “diverse” solutions have received considerable attention in many fields such as artificial intelligence (Hanaka et al., 2021b, a; Baste et al., 2022), machine learning (Gillenwater et al., 2015), and data mining (Wang et al., 2013; Yuan et al., 2016). There are many directions in the research on finding diverse solutions, depending on definitions of solutions and diversity measures. Given these rich applications, the diverse X paradigm was proposed by Fellows and Rosamond in Dagstuhl Seminar 18421 (Fernau et al., 2019). In this paradigm, “X” is a placeholder that represents solutions we are looking for, and they asked for theoretical investigations of finding diverse solutions. Since the problem of finding diverse solutions is much harder than that of finding a single solution for some “X”, it would be reasonable to consider the problem from the perspective of fixed-parameter tractability. From this proposition, several fixed-parameter tractable (FPT) algorithms are developed. Baste et al. gave algorithms for finding diverse solutions related to hitting sets (Baste et al., 2019) and those on bounded-treewidth graphs (Baste et al., 2022). Hanaka et al. (Hanaka et al., 2021b) proposed a framework to obtain FPT algorithms for finding diverse solutions in various combinatorial problems. Fomin et al. (Fomin et al., 2020, 2021) investigated the fixed-parameter tractability of finding diverse solutions related to matchings and matroids. In these results, the running time bounds of these FPT algorithms exponentially depend on the number of solutions we are looking for, which would be prohibitive for computing moderate numbers of solutions.

In this paper, we aim to develop theoretically efficient algorithms for finding moderate numbers of diverse solutions. As we mentioned, the problem of finding diverse solutions is harder than that of finding a single solution. For example, the problem of computing a maximum matching in a graph is known to be solvable in polynomial time, whereas that of computing two maximum matchings $M_{1}$ and $M_{2}$ maximizing $|M_{1}\mathbin{\triangle}M_{2}|$ is known to be NP-hard (Fomin et al., 2020). In this paper, we aim to develop theoretically efficient algorithms for finding moderate numbers of diverse solutions.

Our main result is a framework for designing efficient approximation algorithms with constant approximation factors for finding diverse solutions in combinatorial problems. We employ the sum of pairwise weighted Hamming distances among solutions as our diversity measure (see Section 2 for its definition), while some previous work (Fomin et al., 2021) employs the minimum of weighted Hamming distances. Roughly speaking, our approximation framework says that if we can enumerate top-$k$ weighted solutions in polynomial time, then we can obtain in polynomial time unweighted solutions maximizing our diversity measure with constant approximation factors. Moreover, suppose that we can exactly maximize our diversity of solutions in polynomial time when the number of solutions we are looking for is bounded by a constant. Then, our framework yields a polynomial-time approximation scheme (PTAS), meaning that factor-$(1-\varepsilon)$ approximation in polynomial time for every constant $\varepsilon>0$. By applying our framework, we obtain efficient constant-factor approximation algorithms for finding diverse solutions of matchings in a graph and of common bases of two matroids, while PTASes for finding diverse solutions of minimum cuts and of interval schedulings. Let us note that these diversity maximization problems are unlikely to be solvable in polynomial time, which will be discussed later.

We denote the set of real numbers, the set of non-negative real numbers, and the set of positive real numbers as $\mathbb{R}$, $\mathbb{R}_{\geq 0}$, and $\mathbb{R}_{>0}$, respectively. Let $E$ be a set. We denote the set of all subsets of $E$ as $2^{E}$.

A function $d\colon E\times E\to\mathbb{R}_{\geq 0}$ is called a metric (on $E$) if it satisfies the following conditions: for $x,y,z\in E$, (1) $d(x,y)=0$ if and only if $x=y$; (2) $d(x,y)=d(y,x)$; (3) $d(x,z)\leq d(x,y)+d(y,z)$. Suppose that $E\subseteq\mathbb{R}^{m}$ for some integer $m$. For $x\in E$, we denote by $x_{i}$ the $i$th component of $x$. If $d(x,y)=\sum_{1\leq i\leq m}|x_{i}-y_{i}|$ holds for $x,y\in E$, then $d$ is called an $\ell_{1}$-metric.

Let $E$ be a finite set. For $X,Y\subseteq E$, the symmetric difference between $X$ and $Y$ is denoted by $X\mathbin{\triangle}Y$ (i.e., $X\mathbin{\triangle}Y=(X\setminus Y)\cup(Y\setminus X)$). Let $w:E\to\mathbb{R}_{>0}$. A weighted Hamming distance is a function $d:2^{E}\times 2^{E}\to\mathbb{R}_{\geq 0}$ such that for $X,Y\subseteq E$, $d_{w}(X,Y)=w(X\mathbin{\triangle}Y)$, where $w(Z)=\sum_{x\in Z}w(x)$ for $Z\subseteq E$. Suppose that $E=\{1,2,\ldots,m\}$. We can regard each subset $X\subseteq E$ as an $m$-dimensional vector $x=(x_{1},\ldots,x_{m})$ defined by $x_{i}=w(i)$ if $i\in X$ and $x_{i}=0$ otherwise, for $1\leq i\leq m$. It is easy to observe that for $X,Y\subseteq E$, $d_{w}(X,Y)=\sum_{1\leq i\leq m}|x_{i}-y_{i}|$, where $x$ and $y$ are the vectors corresponding to $X$ and $Y$, respectively. Thus, the weighted Hamming distance $d_{w}$ can be considered as an $\ell_{1}$-metric.

In this paper, we focus on the following diversity measure $d_{\rm sum}(\cdot)$, called the sum diversity. Let ${\mathcal{Y}}=\{Y_{1},\dots,Y_{k}\}$ be a collection of subsets of $E$ and $w\colon E\to\mathbb{R}_{\geq 0}$ be a weight function. We define

Our problem Max-Sum Diverse Solutions is defined as follows.

Each set in $\mathcal{X}$ is called a feasible solution. In Max-Sum Diverse Solutions, the set $\mathcal{X}$ of feasible solutions is not given explicitly, while we can test whether a set $X\subseteq E$ belongs to $\mathcal{X}$. Our problem Max-Sum Diverse Solutions is highly related to the problem of packing disjoint feasible solutions.

This observation implies several hardness results of Max-Sum Diverse Solutions, which will be discussed in Section 4.

We particularly focus on the approximability of Max-Sum Diverse Solutions for specific sets of feasible solutions. For a maximization problem, we say that an approximation algorithm has factor $0<\alpha\leq 1$ if given an instance $I$, the algorithm outputs a solution with objective value ${\rm ALG}(I)$ such that ${\rm ALG}(I)/{\rm OPT}(I)\geq\alpha$, where ${\rm OPT}(I)$ is the optimal value for $I$. A polynomial-time approximation scheme is an approximation algorithm that takes an instance $I$ and a constant $\varepsilon>0$, the algorithm outputs a solution with ${\rm ALG(I)/{\rm OPT}(I)}\geq 1-\varepsilon$ in polynomial time.

In this section, we propose a framework for designing approximation algorithms for Max-Sum Diverse Solutions. The basic strategy to our framework is the local search algorithm described in the previous section. Let $E$ be a finite set and let $\mathcal{X}\subseteq 2^{E}$ be a set of feasible solutions. We set $X\coloneqq\mathcal{X}$ and apply the local search algorithm for Max-Sum Diversification to $(X,d_{w},k)$. Recall that our diversity measure $d_{\rm sum}$ is the sum of weighted Hamming distances $d_{w}$. Moreover, $d_{w}$ is an $\ell_{1}$-metric, as observed in the previous section. By Theorem 4, the local search algorithm for Max-Sum Diversification has approximation factor $1-2/k$. However, the running time of a straightforward application of Lemma 3 is $O(\left|\mathcal{X}\right|\cdot\left|E\right|k^{2}\log k)$ even if the feasible solutions in $\mathcal{X}$ can be enumerated in $O(\left|\mathcal{X}\right|\cdot\left|E\right|)$ total time, which may be exponential in the input size $\left|E\right|$.

A main obstacle to applying the local search algorithm is that from a current set $\mathcal{Y}=\{Y_{1},\ldots,Y_{k}\}$ of feasible solutions, we need to find a pair of feasible solutions $(X,Y)\in(\mathcal{X}\setminus\mathcal{Y})\times\mathcal{Y}$ maximizing $d_{\rm sum}(\mathcal{Y}-Y+X)$. To overcome this obstacle, we exploit top-$k$ enumeration algorithms. Let $w^{\prime}\colon E\to\mathbb{R}$ be a weight function. An algorithm $\mathcal{A}$ is called a top-$k$ enumeration algorithm for $(E,\mathcal{X},w^{\prime},k)$ if for a positive integer $k$, $\mathcal{A}$ finds $k$ feasible solutions $Y_{1},\ldots,Y_{k}\in\mathcal{X}$ such that for any $Y\in\{Y_{1},\ldots,Y_{k}\}$ and $X\in\mathcal{X}\setminus\{Y_{1},\ldots,Y_{k}\}$, $w^{\prime}(X)\leq w^{\prime}(Y)$ holds. By using $\mathcal{A}$, we can compute the pair $(X,Y)$ as follows.

We first guess $Y\in\mathcal{Y}$ in the pair $(X,Y)$ and let $\mathcal{Y}^{\prime}=\mathcal{Y}\setminus\{Y\}$. To find the pair $(X,Y)$, it suffices to find $X\in\mathcal{X}\setminus\mathcal{Y}^{\prime}$ that maximizes $\sum_{Y^{\prime}\in\mathcal{Y}^{\prime}}w(X\triangle Y^{\prime})$. For an element $e\in E$, we define a new weight $w^{\prime}(e)\coloneqq w(e)(\mathit{Ex}(e,\mathcal{Y}^{\prime})-\mathit{In}(e,\mathcal{Y}^{\prime}))$, where $\mathit{In}(e,\mathcal{Y}^{\prime})$ (resp. $\mathit{Ex}(e,\mathcal{Y}^{\prime})$) is the number of feasible solutions in $\mathcal{Y}^{\prime}$ that contain $e$ (resp. do not contain $e$). For notational convenience, we fix $\mathcal{Y}^{\prime}$ and write $\mathit{In}(e)$ and $\mathit{Ex}(e)$ to denote $\mathit{In}(e,\mathcal{Y}^{\prime})$ and $\mathit{Ex}(e,\mathcal{Y}^{\prime})$, respectively. The following lemma shows that a feasible solution $X$ that maximizes $w^{\prime}(X)$ also maximizes $\sum_{Y^{\prime}\in\mathcal{Y}^{\prime}}w(X\mathbin{\triangle}Y^{\prime})$.

From the above lemma, we can find the pair $(X,Y)$ with a top-$k$ enumeration algorithm $\mathcal{A}$ for $(E,\mathcal{X},w^{\prime},k)$ as follows. By Lemma 6, for any feasible solution $X\in\mathcal{X}$, $\sum_{Y^{\prime}\in\mathcal{Y}^{\prime}}w(X\mathbin{\triangle}Y^{\prime})=w^{\prime}(X)+\sum_{e\in E}w(e)\cdot\mathit{In}(e)$. Since the second term does not depend on $X$, to find a feasible solution $X$ maximizing the left-hand side, it suffices to maximize $w^{\prime}(X)$ subject to $X\in\mathcal{X}\setminus\mathcal{Y}^{\prime}$. The algorithm $\mathcal{A}$ allows us to find $k$ feasible solution $Z_{1},\ldots,Z_{k}$ such that $w^{\prime}(Z_{1})\geq\cdots\geq w^{\prime}(Z_{k})\geq w^{\prime}(Z)$ for any feasible solution $Z$ other than $Z_{1},\ldots,Z_{k}$. As $|\mathcal{Y}^{\prime}|<k$, at least one of these solutions provides such a solution $X$.

The entire algorithm is as follows. We first find a set of $k$ distinct feasible solutions in $\mathcal{X}$ using the enumeration algorithm $\mathcal{A}$. Then, we repeat the local update procedure described above $O(k\log k)$ times. Suppose that $\mathcal{A}$ enumerates $k$ feasible solutions in time $O((|E|+k)^{c})$ for some constant $c$. Then, the entire algorithm runs in time $O((|E|+k)^{c}|E|k^{2}\log k)$ as we can compute the pair $(X,Y)$ in time $O((|E|+k)^{c}|E|k)$ by simply guessing $Y\in\mathcal{Y}$.

Note that the approximation factor $1-2/k$ does not give a reasonable bound for $k=2$. In this case, however, we still have an approximation factor $1/2$ with a greedy algorithm for Max-Sum Diversification (Birnbaum and Goldman, 2009), which is described as follows. Initially, we set $\mathcal{Y}=\{Y_{1}\}$ with arbitrary $Y_{1}\in\mathcal{X}$. Then, we compute a feasible solution $Y_{2}\in\mathcal{X}\setminus\mathcal{Y}$ maximizing $\sum_{Y\in\mathcal{Y}}w(Y_{2}\triangle Y)$. By Lemma 6 and the above discussion, we can find such a solution $Y_{2}$ with a top-$k$ enumeration algorithm for $(E,\mathcal{X},w^{\prime},k)$, where $w^{\prime}(e)\coloneqq w(e)\cdot(\mathit{Ex}(e,\mathcal{Y})-\mathit{In}(e,\mathcal{Y}))$ for $e\in E$. We repeat this $k-1$ times so that $\mathcal{Y}$ contains $k$ feasible solutions. As discussed in this section, the approximation factor of this algorithm is $1/2$ as in (Birnbaum and Goldman, 2009). Thus, the following theorem holds.

To complete the description of approximation algorithms based on our framework, we need to develop top-$k$ enumeration algorithms for specific problems. In what follows, we design top-$k$ enumeration algorithms for matchings, common bases of two matroids, and interval schedulings.

Our top-$k$ enumeration algorithms are based on a well-known technique used in (Lawler, 1972) (also discussed in (Eppstein, 2008)). The key to enumeration algorithms is the following Weighted Extension.

If we can solve the above problem in $O(\left|E\right|^{c})$ time, then we can obtain a top-$k$ enumeration algorithm for $(E,\mathcal{X},w^{\prime},k)$ that runs in $O(k\left|E\right|^{c+1})$ time.