A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
January 01, 1970
Abstract
Finding a single best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only “approximately” formulated for original real-world problems. To solve this issue, finding multiple solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.
1 Introduction↩︎
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 [1] 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 [2]–[4], 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 [5]–[7], machine learning [8], and data mining [2], [3]. 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 [9]. 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 [10] and those on bounded-treewidth graphs [7]. Hanaka et al. [5] proposed a framework to obtain FPT algorithms for finding diverse solutions in various combinatorial problems. Fomin et al. [11], [12] 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 [11]. 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 2 for its definition), while some previous work [12] 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.
2 Preliminaries↩︎
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}_{\ge 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}_{\ge 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) \le 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 \le i \le 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}_{\ge 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 \le i \le m\). It is easy to observe that for \(X, Y \subseteq E\), \(d_w(X, Y) = \sum_{1 \le i \le 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}_{\ge 0}\) be a weight function. We define \[d_{\rm sum}(\mathcal{Y}) = \displaystyle\sum_{1 \le i < j \le k} d_w(Y_i, Y_j).\] Our problem Max-Sum Diverse Solutions is defined as follows.
Definition 1 (Max-Sum Diverse Solutions). Given a finite set \(E\), an integer \(k\), a weight function \(w\colon E \to \mathbb{R}_{\ge 0}\), and a membership oracle for \(\mathcal{X} \subseteq 2^E\), the task of Max-Sum Diverse Solutions is to find a set \(\mathcal{Y} = \{Y_1, Y_2, \ldots, Y_k\}\) of \(k\) distinct subsets \(Y_1, Y_2, \ldots, Y_k \in \mathcal{X}\) that maximizes the sum diversity \(d_{\rm sum}(\mathcal{Y})\).
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.
Observation 1. Suppose that all sets in \(\mathcal{X}\) have the same cardinality \(r\) and \(w(e) = 1\) for \(e \in E\). Let \(Y_1, Y_2, \ldots, Y_k \in \mathcal{X}\) be \(k\) distinct subsets. Then, \(d_{\rm sum}(\{Y_1, \ldots, Y_k\}) \ge kr(k - 1)\) if and only if \(Y_i \cap Y_j = \emptyset\) for \(1 \le i < j \le k\).
This observation implies several hardness results of Max-Sum Diverse Solutions, which will be discussed in 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 \le 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) \ge \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)} \ge 1 - \varepsilon\) in polynomial time.
2.1 A technique for Max-Sum Diversification↩︎
Our framework is based on approximation algorithms for a similar problem Max-Sum Diversification. Let \(X\) be a set and let \(d \colon X \times X \to \mathbb{R}_{\ge 0}\) be a metric. In what follows, for \(Y \subseteq X\), we denote \(\sum_{x, y \in Y} d(x, y)\) as \(d(Y)\).
Definition 2 (Max-Sum Diversification). Given a metric \(d\colon X \times X \to \mathbb{R}_{\ge 0}\) on a finite set \(X\) and an integer \(k\), the task of Max-Sum Diversification is to find a subset \(Y \subseteq X\) with \(|Y| = k\) that maximizes \(d(Y)\).
Max-Sum Diversification is studied under various names such as MAX-AVG Facility Dispersion and Remote-clique [13], [14]. Max-Sum Diversification is known to be -hard [14]. Cevallos et al. [13] devised a PTAS for Max-Sum Diversification. Their algorithm is based on a rather simple local search technique, but their analysis of the approximation factor and the iteration bound are highly nontrivial. Our framework for Max-Sum Diverse Solutions is based on their algorithm, which is briefly sketched below.
![Figure 1: A (1-2/k)-approximation algorithm for Max-Sum Diversification [13].](/article/2201.08940/_pdflatex/wtqefohm.png "fig:")
A pseudocode of the algorithm due to [13] is given in 1. In this algorithm, we first pick an arbitrary set of \(k\) elements in \(X\), which is denoted by \(Y \subseteq X\). Then, we find a pair of elements \(x \in X \setminus Y\) and \(y \in Y\) that maximizes \(d(Y - y + x)\) and update \(Y\) by \(Y - y + x\) if \(d(Y - y + x) > d(Y)\). We repeat this update procedure \(\lceil \frac{k(k-1)}{(k+1)} \ln (\frac{(k+2)(k-1)^2}{4}) \rceil = O(k \log k)\) times. Since we can find a pair \((x, y)\) in \(O(\left|X\right|k\tau)\) time, where \(\tau\) is the running time to evaluate the distance function \(d(x, y)\) for \(x, y \in X\), the following lemma holds.
Lemma 1. 1 runs in time \(O(\left|X\right|k^2 \tau \log k)\).
They showed that if the metric \(d\) is negative type, then the approximation ratio of 1 is at least \(1-2/k\) [13]. Here, we do not give the precise definition of a negative type metric but mention that every \(\ell_1\)-metric is negative type [15], [16].
Theorem 1 ([13]). If \(d\colon X \times X \to \mathbb{R}_{\ge 0}\) is a negative type metric, then the approximation ratio of 1 is \(1 - 2/k\).
They further observed that the above theorem implies that Max-Sum Diversification admits a PTAS as follows. Let \(\epsilon\) be a positive constant. When \(\epsilon < 2/k\), that is, \(k < 2/\epsilon\), then \(k\) is constant. Thus, we can solve Max-Sum Diversification in time \(\left|X\right|^{O(1/\epsilon)}\) by using a brute-force search. Otherwise, the above \((1-2/k)\)-approximation algorithm achieves factor \(1-\epsilon\). Thus, Max-Sum Diversification admits a PTAS, provided that \(d\) is a negative type metric.
Corollary 1 ([13]). If \(d\colon X \times X \to \mathbb{R}_{\ge 0}\) is a negative type metric, then Max-Sum Diversification admits a PTAS.
3 A framework for finding diverse solutions↩︎
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 \mathrel{\vcenter{:}}= \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 1, the local search algorithm for Max-Sum Diversification has approximation factor \(1 - 2/k\). However, the running time of a straightforward application of 1 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' \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', 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'(X) \le w'(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}' = \mathcal{Y} \setminus \{Y\}\). To find the pair \((X, Y)\), it suffices to find \(X \in \mathcal{X} \setminus \mathcal{Y}'\) that maximizes \(\sum_{Y' \in \mathcal{Y}'} w(X \triangle Y')\). For an element \(e \in E\), we define a new weight \(w'(e) \mathrel{\vcenter{:}}= w(e)(\mathit{Ex}(e, \mathcal{Y}') - \mathit{In}(e, \mathcal{Y}'))\), where \(\mathit{In}(e, \mathcal{Y}')\) (resp. \(\mathit{Ex}(e, \mathcal{Y}')\)) is the number of feasible solutions in \(\mathcal{Y}'\) that contain \(e\) (resp. do not contain \(e\)). For notational convenience, we fix \(\mathcal{Y}'\) and write \(\mathit{In}(e)\) and \(\mathit{Ex}(e)\) to denote \(\mathit{In}(e, \mathcal{Y}')\) and \(\mathit{Ex}(e, \mathcal{Y}')\), respectively. The following lemma shows that a feasible solution \(X\) that maximizes \(w'(X)\) also maximizes \(\sum_{Y' \in \mathcal{Y}'}w(X \mathbin{\triangle} Y')\).
Lemma 2. For any feasible solution \(X \in \mathcal{X}\), \(\sum_{Y' \in \mathcal{Y}'}w(X \mathbin{\triangle} Y') = w'(X) + \sum_{e \in E}w(e)\cdot\mathit{In}(e)\).
Proof. The contribution of \(e \in X\) to \(w(X \mathbin{\triangle} Y')\) is \(w(e)\) if \(e \not\in Y'\), and \(0\) otherwise. Thus, \(e \in X\) contributes \(w(e)\cdot\mathit{Ex}(e)\) to \(\sum_{Y' \in \mathcal{Y}'}w(X \mathbin{\triangle} Y')\). Similarly, \(e \in E \setminus X\) contributes \(w(e)\cdot \mathit{In}(e)\) to \(\sum_{Y' \in \mathcal{Y}'}w(X \mathbin{\triangle} Y')\). This gives us \(\sum_{Y' \in \mathcal{Y}'}w(X \mathbin{\triangle} Y') = w'(X) + \sum_{e \in E}w(e)\cdot\mathit{In}(e)\) as follows. \[\begin{align} &\sum_{Y' \in \mathcal{Y}'}w(X \mathbin{\triangle} Y') \\ &= \sum_{e \in X}w(e)\cdot \mathit{Ex}(e) + \sum_{e \in E \setminus X}w(e)\cdot \mathit{In}(e)\\ &= \sum_{e \in X}w(e)\cdot \mathit{Ex}(e) + \sum_{e \in E}w(e)\cdot \mathit{In}(e) - \sum_{e \in X}w(e)\cdot \mathit{In}(e) \\ &= \sum_{e \in X}w(e)(\mathit{Ex}(e) - \mathit{In}(e)) + \sum_{e \in E}w(e)\cdot \mathit{In}(e) \\ &= w'(X) + \sum_{e \in E}w(e)\cdot \mathit{In}(e). \qedhere \end{align}\] ◻
From the above lemma, we can find the pair \((X, Y)\) with a top-\(k\) enumeration algorithm \(\mathcal{A}\) for \((E, \mathcal{X}, w', k)\) as follows. By 2, for any feasible solution \(X \in \mathcal{X}\), \(\sum_{Y' \in \mathcal{Y}'}w(X \mathbin{\triangle} Y') = w'(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'(X)\) subject to \(X \in \mathcal{X} \setminus \mathcal{Y}'\). The algorithm \(\mathcal{A}\) allows us to find \(k\) feasible solution \(Z_1, \ldots, Z_k\) such that \(w'(Z_1) \ge \cdots \ge w'(Z_k) \ge w'(Z)\) for any feasible solution \(Z\) other than \(Z_1, \ldots, Z_k\). As \(|\mathcal{Y}'| < 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 [17], 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 2 and the above discussion, we can find such a solution \(Y_2\) with a top-\(k\) enumeration algorithm for \((E, \mathcal{X}, w', k)\), where \(w'(e) \mathrel{\vcenter{:}}= 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 [17]. Thus, the following theorem holds.
Theorem 2. Let \(E\) be a finite set, \(\mathcal{X} \subseteq 2^E\), and \(w\colon E \to \mathbb{R}_{> 0}\). Suppose that there is a top-\(k\) enumeration algorithm for \((E, \mathcal{X}, w', k)\) that runs in \(O((\left|E\right| + k)^c)\) time for a constant, where \(w'\colon E\to \mathbb{R}\) is an arbitrary weight function. Then, there is an \(\alpha\)-approximation algorithm for Max-Sum Diverse Solutions that runs in \(O((\left|E\right| + k)^{c} |E| k^2\log k)\) time, where \(\alpha = \max(1 - 2/k, 1/2)\). Moreover, if there is a polynomial-time exact algorithm for Max-Sum Diverse Solutions for constant \(k\), then it admits a PTAS.
4 Applications of the framework↩︎
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 [18] (also discussed in [1]). The key to enumeration algorithms is the following Weighted Extension.
Definition 3 (Weighted Extension). Given a finite set \(E\), a set of feasible solutions \(\mathcal{X} \subseteq 2^E\) as a membership oracle, a weight function \(w'\colon E \to \mathbb{R}\), and a pair of disjoint subsets \(\mathit{In}\) and \(\mathit{Ex}\) of \(E\), the task is to find a feasible solution \(X \in \mathcal{X}\) that satisfies \(\mathit{In} \subseteq X\) and \(X\cap \mathit{Ex} = \emptyset\) maximizing \(w'(X)\) subject to these conditions.
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', k)\) that runs in \(O(k\left|E\right|^{c+1})\) time.
Lemma 3 ([18]). Suppose that Weighted Extension for \((E, \mathcal{X}, w', k)\) can be solved in \(O(\left|E\right|^c)\) time. Then, there is an \(O(k\left|E\right|^{c+1})\)-time top-\(k\) enumeration algorithm for \((E, \mathcal{X}, w', k)\).
4.1 Matchings↩︎
Matching is one of the most fundamental combinatorial objects in graphs, and the polynomial-time algorithm for computing a maximum weight matching due to [19] is a cornerstone result in this context. Finding diverse matchings has also been studied so far [5], [6], [11], [12]. Let \(G = (V, E)\) be a graph. A set of edges \(M\) is a matching of \(G\) if \(M\) has no pair of edges that share a common endpoint. A matching \(M\) is called a perfect matching of \(G\) if every vertex in \(G\) is incident to an edge in \(M\). By using our framework, we design an approximation algorithm for finding diverse matchings. The formal definition of the problem is as follows.
Definition 4 (Diverse Matchings). Given a graph \(G = (V, E)\), a weight function \(w\colon E\to \mathbb{R}_{> 0}\), and integers \(k\) and \(r\), the task of Diverse Matchings is to find \(k\) distinct matchings \(M_1, \ldots, M_k\) of size \(r\) that maximize \(d_{\rm sum}(\{M_1, \ldots, M_k\})\).
To apply our framework, it suffices to show that Weighted Extension for matchings can be solved in polynomial time. Our method is similar to a reduction from the maximum weight perfect matching problem to the maximum weight matching problem [20]. Let \(\mathit{In}, \mathit{Ex} \subseteq E\) be disjoint subsets of edges and let \(w'\colon E \to \mathbb{R}\). Then, our goal is to find a matching \(M\) of \(G\) with \(|M| = r\) such that \(\textit{In} \subseteq M\) and \(\textit{Ex} \cap M = \emptyset\), and \(M\) maximizes \(w'(M)\) subject to these constraints. This problem can be reduced to that of finding a maximum weight perfect matching as follows. We assume that \(\textit{In}\) is a matching of \(G\) as otherwise there is no matching containing it. Let \(G' = (V', E')\) be the graph obtained from \(G\) by removing (1) all edges in \(\textit{Ex}\) and (2) all end vertices of edges in \(\textit{In}\). Then, it is easy to see that \(M\) is a matching of \(G\) with \(\textit{In} \subseteq M\) and \(\textit{Ex} \cap M = \emptyset\) if and only if \(M \setminus \textit{In}\) is a matching of \(G'\). Thus, it suffices to find a maximum weight matching of size exactly \(r' = r - \left|\textit{In}\right|\) in \(G'\). To this end, we add \(|V'| - 2r'\) vertices \(U\) to \(G'\) and add all possible edges between vertices \(v \in V'\) and \(u \in U\). The graph obtained in this way is denoted by \(H = (V' \cup U, E \cup F)\), where \(F = \{\{u, v\} : u \in U, v \in V'\}\). We extend the weight function \(w'\) by setting \(w'(f) = 0\) for \(f \in F\). Then, the following lemma holds.
Lemma 4. Let \(M^*\) be a maximum weight perfect matching in \(H\). Then, \(M^* \setminus F\) is a matching of size \(r'\) in \(G'\) such that for every size-\(r'\) matching \(M'\) in \(G'\), it holds that \(w'(M') \le w'(M^* \setminus F)\).
Proof. Since \(M^*\) is a perfect matching and any edge incident to \(U\) is contained in \(F\), \(M^*\) must contain exactly \(|U|\) edges of \(F\). This implies that the perfect matching \(M^*\) contains exactly \(r'\) edges of \(G'\). Suppose that there is a size-\(r'\) matching \(M'\) in \(G'\) such that \(w'(M') > w'(M^* \setminus F)\). As every vertex in \(U\) is adjacent to \(V'\), we can choose exactly a set \(N \subseteq F\) of \(|U|\) edges between \(U\) and \(V'\) so that \(M' \cup N\) forms a perfect matching in \(H\). Then, we have \(w'(M' \cup N) = w'(M') + w'(N) > w'(M^* \setminus F) + w'(M^* \cap F) = w'(M^*)\) as \(w'(N) = w'(M^* \cap F) = 0\), contradicting the fact that \(M^*\) is a maximum weight perfect matching of \(H\). ◻
Thus, we can solve Weighted Extension for a size-\(r\) matching in polynomial time [19]. By 2 and 3, we have the following theorem.
Theorem 3. There is a polynomial-time approximation algorithm for Diverse Matchings with approximation factor \(\max(1 - 2/k, 1/2)\).
4.2 Common bases of two matroids↩︎
Let \(E\) be a finite set and let a non-empty family of subsets \(\mathcal{I}\) of \(E\). The pair \(\mathcal{M} = (E, \mathcal{I})\) is a matroid if (1) for each \(X \in \mathcal{I}\), every subset of \(X\) is included in \(\mathcal{I}\) and (2) if \(X, Y \in \mathcal{I}\) and \(\left|X\right| < \left|Y\right|\), then there exists an element \(e \in Y \setminus X\) such that \(X \cup \{e\} \in \mathcal{I}\). Each set in \(\mathcal{I}\) is called an independent set of \(\mathcal{M}\). An inclusion-wise maximal independent set \(I\) of \(\mathcal{M}\) is a base of \(\mathcal{M}\). Because of condition (2), all bases in \(\mathcal{M}\) have the same cardinality. For two matroids \(\mathcal{M}_1 = (E, \mathcal{I}_1)\) and \(\mathcal{M}_2 = (E, \mathcal{I}_2)\), a subset \(X \subseteq E\) is a common base of \(\mathcal{M}_1\) and \(\mathcal{M}_2\) if \(X\) is a base of both \(\mathcal{M}_1\) and \(\mathcal{M}_2\). In this subsection, we give an approximation algorithm for diverse common bases of two matroids.
Definition 5 (Diverse Matroid Common Bases). Given two matroids \(\mathcal{M}_1 = (E, \mathcal{I}_1)\) and \(\mathcal{M}_2 = (E, \mathcal{I}_2)\) as membership oracles, a weight function \(w\colon E \to \mathbb{R}_{> 0}\), and an integer \(k\), the task of Diverse Matroid Common Basesis to find \(k\) distinct common bases \(B_1, \ldots, B_k\) of \(\mathcal{M}_1\) and \(\mathcal{M}_2\) that maximize \(d_{\rm sum}(B_1, \ldots, B_k)\).
Given two matroids \(\mathcal{M}_1 =(E,\mathcal{I}_1)\) and \(\mathcal{M}_2 =(E,\mathcal{I}_2)\) as membership oracles, the problem of partitioning \(E\) into \(k\) common bases of \(\mathcal{M}_1\) and \(\mathcal{M}_2\) is a notoriously hard problem, which requires an exponential number of membership queries [21]. This fact together with 1 implies that Diverse Matroid Common Bases cannot be solved with polynomial number of membership queries in our problem setting. Given this fact, we develop a constant-factor approximation algorithm for Diverse Matroid Common Bases. To this end, we show that Weighted Extension for common bases of two matroids can be solved in polynomial time.
Similarly to the case of matchings, we can find a maximum weight common base \(B \in \mathcal{I}_1 \cap \mathcal{I}_2\) subject to \(\mathit{In} \subseteq B\) and \(\mathit{Ex} \cap B = \emptyset\) for given disjoint \(\mathit{In}, \mathit{Ex} \subseteq E\), which is as follows. Let \(\mathcal{M} = (E, \mathcal{I})\) be a matroid. For \(X \subseteq E\), we let \(\mathcal{M} \setminus X = (E \setminus X, \mathcal{J})\), where \(\mathcal{J} = \{J \setminus X : J \in \mathcal{I}\}\). Then, \(\mathcal{M} \setminus X\) is a matroid (see [22]). Similarly, for \(X \subseteq E\), we let \(\mathcal{M} \slash X = (E \setminus X, \mathcal{J}')\), where \(\mathcal{J}' = \{J : J \cup X \in \mathcal{I}, J \subseteq E \setminus X\}\). Then \((E, \mathcal{J})\) is also a matroid (see [22]). For two matroids \(\mathcal{M}_1\) and \(\mathcal{M}_2\), we consider two matroids \(\mathcal{M}'_1 = (\mathcal{M}_1 \setminus \mathit{Ex}) \slash \mathit{In}\) and \(\mathcal{M}'_2 = (\mathcal{M}_2 \setminus \mathit{Ex}) \slash \mathit{In}\). For every independent set \(X\) in \(\mathcal{M}'_1\) and \(\mathcal{M}'_2\), \(X\) does not contain any element in \(\mathit{Ex}\) and \(X \cup \mathit{In}\) is an independent set in both \(\mathcal{M}_1\) and \(\mathcal{M}_2\). Thus, Weighted Extension can be solved by computing a maximum weight common base in \(\mathcal{M}'_1\) and \(\mathcal{M}'_2\), which can be solved in polynomial time (see Theorem 41.7 in [23]). By 2 and 3, the following theorem holds.
Theorem 4. There is a polynomial-time approximation algorithm for Diverse Matroid Common Bases with approximation factor \(\max(1 - 2/k, 1/2)\), provided that the membership oracles for \(\mathcal{M}_1\) and \(\mathcal{M}_2\) can be evaluated in polynomial time.
4.3 Minimum cuts↩︎
Let \(G = (V, E)\) be a graph. A partition of \(V\) into two non-empty sets \(A\) and \(B\) is called a cut of \(G\). For a cut \((A, B)\) of \(G\), the set of edges having one end in \(A\) and the other end in \(B\) is denoted by \(E(A, B)\). When no confusion arises, we may refer to \(E(A, B)\) as a cut of \(G\). The size of a cut \(C = E(A, B)\) is defined by \(|E(A, B)|\). A cut \(C\) is called a minimum cut of \(G\) if there is no cut \(C'\) of \(G\) with \(|C'| < |C|\). In this section, we consider the following problem.
Definition 6 (Diverse Minimum Cuts). Given a graph \(G = (V, E)\) with an edge-weight function \(w\colon E \to \mathbb{R}_{\ge 0}\) and an integer \(k\), the task of Diverse Minimum Cuts is to find \(k\) distinct minimum cuts \(C_1, \ldots, C_k \subseteq E\) of \(G\) that maximize \(d_{\rm sum}(\{C_1, \ldots, C_k\})\).
An important observation for this problem is that the number of minimum cuts of any graph \(G\) is \(O(|V|^2)\) [24]. Moreover, we can enumerate all minimum cuts in a graph in polynomial time [25], [26]. Thus, we can solve both Weighted Extension for minimum cuts and Diverse Minimum Cuts for constant \(k\) in polynomial time, yielding a PTAS for Diverse Minimum Cuts.
Theorem 5. Diverse Minimum Cuts admits a PTAS.
Given this, it is natural to ask whether Diverse Minimum Cuts admits a polynomial-time algorithm. However, we show that Diverse Minimum Cuts is -hard even if \(G\) has a cut of size \(3\). Let \(\lambda(G)\) be the size of a minimum cut of \(G\).
Theorem 6. Diverse Minimum Cuts is -hard even if \(\lambda(G) = 3\).
The -hardness is shown by performing a polynomial-time reduction from the maximum independent set problem on cubic graphs, which is known to be -complete [27]. For a graph \(H\), we denote by \(\alpha(H)\) the maximum size of an independent set of \(H\). Let \(H\) be a graph in which every vertex has degree exactly \(3\). Let \(H'\) be the graph obtained from \(H\) by subdividing each edge twice, that is, each edge is replaced by a path of three edges. The set of vertices in \(H'\) that do not appear in \(H\) is denoted by \(D\). The following folklore lemma ensures that the value of \(\alpha\) increases exactly by \(m\).
Lemma 5 (folklore). Let \(m\) be the number of edges in \(H\). Then, \(\alpha(H') = \alpha(H) + m\).
We construct a graph \(G = (V, E)\) from \(H'\) by adding a new vertex \(v^*\) and adding an edge between \(v^*\) and each vertex in \(D\). Note that the degree of \(v^*\) in \(H'\) is more than \(3\).
Lemma 6. \(G\) has \(k\) edge-disjoint cuts of size \(3\) if and only if \(H'\) has an independent set of size \(k\).
Proof. Suppose first that \(H'\) has an independent set \(S\) of size \(k\). Since every vertex in \(S\) appears also in \(G\), we can construct a cut of the form \(C_i = E_G(\{v_i\}, V \setminus \{v_i\})\) for each \(v_i \in S\). As \(S\) is an independent set of \(G\), these \(k\) cuts are edge-disjoint. Moreover, these cuts have exactly three edges since every vertex in \(S\) has degree \(3\) in \(G\). Thus, \(G\) has \(k\) edge-disjoint cuts of size \(3\).
Conversely, suppose \(G\) has \(k\) edge-disjoint cuts \(C_1, C_2, \ldots, C_k \subseteq E\) with \(|C_i| = 3\) for \(1 \le i \le k\). It suffices to prove that each of these cuts forms \(C_i = E_G(\{v\}, V \setminus \{v\})\) for some \(v \in V \setminus \{v^*\}\). Let \(C_i = E_G(X, V \setminus X)\) for some \(X \subseteq V\). Without loss of generality, we assume that \(v^* \in V \setminus X\). In the following, we show that \(X\) contains exactly one vertex. Since every vertex in \(D\) is adjacent to \(v^*\), \(X\) contains at most three vertices of \(D\). Suppose first that \(|X \cap D| = 3\). Since every vertex of \(D\) has a neighbor in \(D\), \(V \setminus X\) has a vertex in \(D\) that has a neighbor in \(X \cap D\). However, as every vertex of \(X \cap D\) is adjacent to \(v^*\), there are at least four edges between \(X\) and \(V \setminus X\), contradicting to the fact that \(|C_i| = 3\).
Suppose next that \(|X \cap D| = 2\). Let \(u, v \in X \cap D\) be distinct. If \(u\) is not adjacent to \(v\), there are two vertices \(u'\) and \(v'\) in \((V \setminus X) \cap D\) that are adjacent to \(u\) and \(v\), respectively. This implies \(C_i\) contains four edges \(\{u, u'\}, \{v, v'\}, \{u, v^*\}, \{v, v^*\}\), yielding a contradiction. Thus, \(u\) is adjacent to \(v\). Let \(u'\) and \(v'\) be the vertices in \(V \setminus (D \cup \{v^*\})\) that are adjacent to \(u\) and \(v\), respectively. Observe that at least one of \(u'\) and \(v'\), say \(u'\), belongs to \(X\) as otherwise there are four edges (\(\{u, u'\}, \{v, v'\}, \{u, v^*\}, \{v, v^*\}\)) between \(X\) and \(V \setminus X\). Since \(|X \cap D| = 2\) and \(u'\) has three neighbors in \(D\), the other two neighbors of \(u'\) belongs to \(V \setminus D\), which ensures at least four edges between \(X\) and \(V \setminus X\).
Suppose that \(|X \cap D| = 1\). Let \(u \in X \cap D\). In this case, we show that \(X = \{u\}\). To see this, consider the neighbors of \(u\). Since \(v^* \in V \setminus X\) and \(|X \cap D| = 1\), at least two neighbors of \(u\), which are \(v^*\) and a vertex in \(D\), belong to \(V \setminus X\). If the other neighbor \(v\) is in \(X\), then by the assumption that \(|X \cap D| = 1\), the two neighbors of \(v\) other than \(u\) belong to \(V \setminus X\), which implies there are at least four edges between \(X\) and \(V \setminus X\). Thus, all the neighbors of \(u\) belong to \(V \setminus X\). Since \(G\) is connected, all the vertices except for \(u\) belong to \(V \setminus X\) as well. Thus, we have \(C_i = E_G(\{u\}, V \setminus \{u\})\).
Finally, suppose that \(X \cap D = \emptyset\). In this case, at least one vertex of \(V \setminus (D \cup \{v^*\})\) is included in \(X\). Let \(u \in X \setminus (D \cup \{v^*\})\). Since \(X \cap D = \emptyset\), every neighbor of \(u\) belongs to \(V \setminus D\). Similarly to the previous case, we have \(X = \{u\}\), which completes the proof. ◻
Note that the proof of 6 also shows that the graph constructed in the reduction has no cut of size at most two. Therefore, by [lem:subdivide-is,lem:cut-is], 6 follows.
When \(\lambda(G) = 1\), then Diverse Minimum Cuts is trivially solvable in linear time as the problem can be reduced to finding all bridges in \(G\). If \(\lambda(G) = 2\), the problem is slightly nontrivial, which in fact is solvable in polynomial time as well.
Theorem 7. Diverse Minimum Cuts can be solved in \(\left|V\right|^{O(1)}\) time, provided that \(\lambda(G) \le 2\).
We reduce the problem to that of finding a subgraph of prescribed size with maximizing the sum of convex functions on their degrees of vertices.
Theorem 8 ([28]). Given an undirected graph \(H\), an integer \(k\), and convex functions \(f_v: \mathbb{N}_{\ge 0} \to \mathbb{R}\) for \(v \in V(H)\), the problem of finding \(k\)-edge subgraph \(H'\) of \(H\) maximizing \(\sum_{v \in V(H)} f_v(d_{H'}(v))\) is solvable in polynomial time, where \(d_{H'}(v)\) is the degree of \(v\) in \(H'\).
We first enumerate all minimum cuts of \(G\) in polynomial time. If \(G\) has no \(k\) minimum cuts, then the instance is trivially infeasible. Suppose otherwise. We construct a graph \(H\) whose vertex set corresponds to \(E\), and the edge set of \(H\) is defined as follows. For each pair \(e, f \in E\), we add an edge between \(e\) and \(f\) to \(H\) if \(\{e, f\}\) is a cut of \(G\). Obviously, the graph \(H\) can be constructed in polynomial time. For each \(e \in E\), we let \(f_e(i) := w(e) \cdot i \cdot (k - i)\) for \(0 \le i \le k\) and \(f_e(i) = \infty\) for \(i > k\). Clearly, the function \(f_e\) is convex. Let \(C_1, \ldots, C_k \subseteq E\) be \(k\) minimum cuts of \(G\). For each \(e\), we denote by \(m(e)\) the number of occurrences of \(e\) among \(C_1, \ldots, C_k\). Since each edge in \(E\) contributes \(w(e) \cdot m(e) \cdot (k - m(e))\) to \(d_{\rm sum}(\{C_1, \ldots, C_k\})\), we immediately have the following lemma.
Lemma 7. \(H\) has a subgraph \(H'\) of \(k\) edges such that \(\sum_{v \in V(H)} f_e(d_{H'}(e)) \ge t\) if and only if there are \(k\) edge cuts \(C_1, \ldots, C_k \subseteq E\) of \(G\) with \(|C_i| = 2\) for \(1 \le i \le k\) such that \(d_{\rm sum}(\{C_1, \ldots, C_k\}) \ge t\).
By 7 and 8, Diverse Minimum Cuts can be solved in \(\left|V\right|^{O(1)}\) time, proving 7.
4.4 Interval schedulings↩︎
For a pair of integers \(a\) and \(b\) with \(a \le b\), the set of all numbers between \(a\) and \(b\) is denoted by \([a, b]\). We call \(I = [a, b]\) an interval. For a pair of intervals \(I = [a, b]\) and \(J = [c, d]\), we say that \(I\) overlaps \(J\) if \(I \cap J\neq \emptyset\). For a set of intervals \(\mathcal{S} = \{I_1, \ldots, I_r\}\), we say that \(\mathcal{S}\) is a valid scheduling (or simply a scheduling) if for any pair of intervals \(I_i, I_j \in \mathcal{S}\), \(I_i\) does not overlap \(I_j\). In particular, we call \(\mathcal{S}\) an \(r\)-scheduling if \(\left|\mathcal{S}\right| = r\) for \(r \in \mathbb{N}\). In this section, we deal with the following problem.
Definition 7 (Diverse Interval Schedulings). Given a set of intervals \(\mathcal{I} = \{I_1, \ldots, I_n\}\), a weight function \(w\colon \mathcal{I} \to \mathbb{R}_{> 0}\), and integers \(k\) and \(r\), the task of Diverse Interval Schedulings is to find \(k\) distinct \(r\)-schedulings \(\mathcal{S}_1, \ldots, \mathcal{S}_k \subseteq \mathcal{I}\) that maximize \(d_{\rm sum}(\{\mathcal{S}_1, \ldots, \mathcal{S}_k\})\).
Since the problem of partitioning a set of intervals \(\mathcal{I}\) into \(k\) scheduling \(\mathcal{S}_1, \ldots, \mathcal{S}_k\) such that each \(\mathcal{S}_i\) has exactly \(r\) intervals is known to be NP-hard [29], [30]1, by 1, we have the following theorem.
Theorem 9. Diverse Interval Schedulings is -hard.
To apply 2 to Diverse Interval Schedulings, it suffices to give a polynomial-time algorithm for Weighted Extension for interval schedulings. Observe that if \(\mathit{In}\) is not a scheduling, then there is no scheduling containing \(\mathit{In}\). Observe also that we can remove all intervals included in \(\mathit{Ex}\) or overlapping some interval in \(\mathit{In}\). Thus, the problem can be reduced to the one for finding a maximum weight scheduling with cardinality \(r' = r - \left|\mathit{In}\right|\). This problem can be solved in polynomial time by using a simple dynamic programming approach.
Lemma 8. Given a set \(\mathcal{I}\) and \(w'\colon \mathcal{I} \to \mathbb{R}\) and \(r' \in \mathbb{N}\), there is a polynomial-time algorithm finding a maximum weight \(r'\)-scheduling in \(O(\left|\mathcal{I}\right|^2r')\) time.
Proof. The algorithm is analogous to that to find a maximum weight independent set on interval graphs, which is roughly sketched as follows. We assume that \(\mathcal{I} = \{I_1, I_2, \ldots, I_n\}\) is sorted with respect to their right end points. We define \({\rm opt}(p, q)\) as the maximum total weight of a \(q\)-scheduling \(\mathcal{S}\) in \(\{I_1, I_2, \ldots, I_p\}\) such that \(I_p \in \mathcal{S}\) for \(0 \le p \le n\) and \(0 \le q \le r'\). Then, the values of \({\rm opt}(p, q)\) for all \(p\) and \(q\) can be computed by a standard dynamic programming algorithm in time \(O(\left|\mathcal{I}\right|^2r')\). ◻
By 2 and 3, we obtain a polynomial-time approximation algorithm for Diverse Interval Schedulings with factor \(\max(1 - 2/k, 1/2)\).
Finally, we show that Diverse Interval Schedulings can be solved in polynomial time for fixed \(k\) using a dynamic programming approach, which implies a PTAS for Diverse Interval Schedulings.
Similarly to the proof of 8, assume that \(\mathcal{I} = \{I_1, I_2, \ldots, I_n\}\) is sorted with respect to their right end points. Let \([k] = \{1, 2, \ldots, k\}\). For each \(0 \le p \le \left|\mathcal{I}\right|\), we consider a tuple \(T = (p, L, R, \Gamma)\), where \(L\) and \(R\) are vectors in \(([n] \cup \{0\})^k\) and \(([r] \cup \{0\})^k\), respectively, and \(\Gamma\) is a subset of \(\binom{[k]}{2}\). Clearly, the number of tuples is \(O(n(n+1)^k(r+1)^k2^{\binom{k}{2}})\), which is polynomial when \(k\) is a constant. We denote by \(\ell_i\) and \(r_i\) the \(i\)th component of \(L\) and \(R\), respectively. For a tuple \(T = (p, L, R, \Gamma)\), the value \({\rm opt}(T)\) is the maximum value of \(d_{\rm sum}(\{\mathcal{S}_1, \ldots, \mathcal{S}_k\})\) for \(k\) schedulings under the following four conditions: (1) the maximum index of an interval in \(\bigcup_{1\le i\le k} \mathcal{S}_i\) is \(p\) (\(p = 0\) if \(\bigcup_{1\le i\le k} \mathcal{S}_i = \emptyset\)); (2) for \(1 \le i \le k\), the maximum index of an interval in \(\mathcal{S}_i\) is \(\ell_i\) (\(\ell_i = 0\) if \(\mathcal{S}_i = \emptyset\)); (3) for \(1 \le i \le k\), \(\left|\mathcal{S}_i\right| = r_i\); and (4) for \(1 \le i < j \le k\), \(\{i, j\} \in \Gamma\) if and only if \(\mathcal{S}_i\) and \(\mathcal{S}_j\) are distinct.
We define \({\rm opt}(T) = -\infty\) if no such a set of scheduings exists. When \(R = (r, r, \ldots, r)\) and \(\Gamma = \binom{[k]}{2}\), there is a set of \(k\) distinct \(r\)-schedulings that have the sum diversity \({\rm opt}(T)\) unless \({\rm opt}(T) = -\infty\). For a tuple \(T\), we say that a set of \(k\) schedulings is valid for \(T\) if it satisfies the above four conditions. Hence, among the tuples of the form \((p, L, R, \Gamma)\) with \(R = (r, \ldots, r)\) and \(\Gamma = \binom{[k]}{2}\), \({\rm opt}(T)\) is the optimal value for Diverse Interval Schedulings. We next explain the outline of our dynamic programming algorithm to compute \({\rm opt}(T)\) for any \(T\).
As a base case, \(p = 0\), \(L = (0, \ldots, 0)\), \(R = (0, \ldots, 0)\), and \(\Gamma = \emptyset\) if and only if \({\rm opt}(T) = 0\). Let \(T'\) be a tuple \((p', L', R', \Gamma')\) that satisfies the following conditions: (1)\(p' < p\); (2) for any \(1 \le i \le k\), \(\ell'_i \le \ell_i\) and \(r'_i \le r_i\); and (3) \(\Gamma' \subseteq \Gamma\). We say that a tuple \(T'\) satisfying the above conditions is dominated by \(T\). We denote the set of tuples dominated by \(T\) as \(D(T)\). Let \(C(T) = \{i : \ell_i = p\}\). A tuple \(T'\) is valid for \(T\) if \(T'\) satisfies the following conditions: (1) \(T' \in D(T)\); (2) if \(i \in C(T)\) and \(\ell_i > 0\), then interval \(I_{\ell_i}\) does not overlap with \(I_p\); (3) if \(i \in C(T)\), \(r'_i = r_i - 1\), otherwise, \(r'_i = r_i\); and (4) \(\Gamma = \Gamma' \cup P(T)\) with \(P(T) \mathrel{\vcenter{:}}= \{\{i, j\} \in \binom{[k]}{2} : \left|\{i, j\} \cap C(T)\right| = 1\}\). We denote the set of valid tuples for \(T\) as \(V(T)\). We compute \({\rm opt}(T)\) using the following lemma.
Lemma 9. For a tuple \(T\), \[\begin{align} {\rm opt}(T) = \underset{T' \in V(T)}{\max}({\rm opt}(T') + w(I_p)\cdot \left|C(T)\right|\cdot(k - \left|C(T)\right|)). \end{align}\]
Proof. Let \(T = (p, L, R, \Gamma)\). Let \(\mathcal{S} = \{\mathcal{S}_1, \ldots, \mathcal{S}_k\}\) be a valid set of schedulings with \(d_{\rm sum}(\{\mathcal{S}_1, \ldots, \mathcal{S}_j\}) = {\rm opt}(T)\). Then, \(\mathcal{S}' = (\mathcal{S}_1 \setminus \{I_p\}, \ldots, \mathcal{S}_k \setminus \{I_p\})\) is a valid set of scheduings for \(T' \in V(T)\). Moreover, \(d_{\rm sum}(\mathcal{S}) = d_{\rm sum}(\mathcal{S}') + w(I_p) \cdot |C(T)| \cdot (k - |C(T)|)\) as \(I_p\) contributes \(w(I_p) \cdot |C(T)| \cdot (k - |C(T)|)\) to the diversity. Thus, the left-hand side is at most the right-hand side.
Conversely, let \(T'\) be a tuple maximizing the left-hand side and let \(\mathcal{S}' = \{\mathcal{S}'_1, \ldots, \mathcal{S}'_k\}\) be a valid set of schedulings for \(T'\). For each \(1 \le i \le k\), we set \(\mathcal{S}_i = \mathcal{S}'_i \cup \{I_p\}\) if \(i \in C(T)\) and \(\mathcal{S}_i = \mathcal{S}'_i\) otherwise. By condition (2) in the definition of a valid tuple, each interval in \(\mathcal{S}'_i\) does not overlap with \(I_p\), meaning that \(\mathcal{S}_i\) is a scheduling. Thus, the right-hand side is at most the left-hand side. ◻
From the above lemma, we can compute \({\rm opt}(T)\) for any \(T\) in polynomial time when \(k\) is a constant. Moreover, from \({\rm opt}(T)\), we can find \(k\) schedulings with the maximum sum diversity by a standard trace back technique. Combining the approximation algorithm and the above algorithm, we obtain a PTAS.
Theorem 10. Diverse Interval Schedulings admits a PTAS.
5 Conclusion↩︎
In this paper, we give a framework for designing approximation algorithms for Max-Sum Diverse Solutions. This framework runs in \({\rm poly}(\left|E\right| + k)\) time and versatile, which can be applied to the diverse version of several well-studied combinatorial problems, i.e., Diverse Matchings, Diverse Matroid Common Bases, Diverse Minimum Cuts, and Diverse Interval Schedulings. The key to applying our framework is the polynomial-time solvability of Weighted Extension, which yields constant-factor approximation algorithms for Diverse Matchings and Diverse Matroid Common Bases. Moreover, we obtain a PTAS for Max-Sum Diverse Solutions if we can solve the problem in polynomial time for fixed \(k\), yielding PTASes for Diverse Minimum Cuts and Diverse Interval Schedulings.
References↩︎
Note that the NP-hardness is proven for the case that each \(\mathcal{S}_i\) has at most \(r\) intervals, but a simple reduction proves the NP-hardness of this variant.↩︎