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

Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota OtachiAAAI 2023 · DOI

Introduction

In traditional combinatorial optimization, the standard paradigm is to identify a single optimal solution—such as the shortest path in a network or the maximum matching in a graph. However, mathematical models often fail to capture the full complexity of real-world scenarios. Implicit constraints, subjective preferences, and noisy data mean that the "optimal" solution in a model might be impractical in reality.

To address this, researchers have turned toward finding a diverse set of solutions. By providing a "catalog" of high-quality solutions that are structurally distinct from one another, algorithms can empower human decision-makers to select the option that best fits the actual, unmodeled context. This paper introduces a general algorithmic framework to achieve this diversity across a variety of classic combinatorial problems.

The Challenge of Diversity

Finding a set of $k$ solutions that maximizes diversity is significantly more complex than finding a single optimal one. Even when the underlying problem is solvable in polynomial time, maximizing a diversity metric—such as the Hamming distance between solutions—is typically NP-hard.

The authors focus specifically on the Max-Sum Hamming Distance. In this formulation, the goal is to select $k$ feasible solutions such that the sum of the distances between all pairs in the set is maximized. While maximizing the minimum distance between any two solutions (Max-Min) is notoriously difficult, the Max-Sum approach is more algorithmically tractable while still ensuring the resulting set is broadly representative of the solution space.

The Algorithmic Framework

The core of the paper is a framework that reduces the diversity problem to a more manageable sub-problem: top-$k$ weighted enumeration.

1. Local Search and Swapping

The framework utilizes a local search algorithm adapted from "dispersion problems" in metric spaces. Starting with an arbitrary set of $k$ feasible solutions, the algorithm repeatedly attempts to swap one solution in the set for a "better" one outside the set that increases the total diversity of the collection.

2. The Weighted Extension Trick

The key technical contribution is the "Weighted Extension" trick. The authors demonstrate that finding the optimal candidate to swap into the set can be treated as finding a maximum weight solution in the original problem space. They prove that if a problem allows for efficient weighted enumeration (the ability to find the $k$-best solutions for a weighted version of the problem), it can be plugged into this framework to produce a diverse set.

3. Theoretical Foundations

The authors leverage the fact that weighted Hamming distance can be viewed as an $\ell_1$-metric, which belongs to the class of "negative type" metrics. This connection allows the framework to provide a $\max(1 - 2/k, 1/2)$-approximation. Furthermore, if the problem can be solved exactly for a constant $k$, the framework yields a Polynomial Time Approximation Scheme (PTAS).

Applications and Results

The framework was applied to several landmark problems in combinatorial optimization, yielding the first known approximation guarantees for their diverse variants:

  • Diverse Matchings: Obtained a constant-factor approximation algorithm.
  • Diverse Matroid Common Bases: Obtained a constant-factor approximation. This is particularly notable as finding even two common bases can be difficult in general settings.
  • Diverse Minimum Cuts: While the authors proved this problem is NP-hard even for small cut sizes, they provided a PTAS using the framework.
  • Diverse Interval Scheduling: The authors developed a new dynamic programming approach for the weighted extension sub-problem, resulting in a PTAS.

Limitations and Future Directions

While the framework provides a robust toolkit for diversity, it is currently specialized for the Max-Sum Hamming distance. It does not yet extend to Max-Min distance measures, which are sometimes preferred when a guarantee is needed that no two solutions are too similar.

Additionally, the current framework focuses on finding diverse unweighted solutions (where all feasible solutions are treated as equally valid). A natural next step for this research is to develop methods that balance diversity with high individual objective values, ensuring that the solutions in the catalog are not only different but also high-performing according to the original cost function.

Summary updated

BibTeX
@inproceedings{hanaka2023framework,
  author = {Tesshu Hanaka and Masashi Kiyomi and Yasuaki Kobayashi and Yusuke Kobayashi and Kazuhiro Kurita and Yota Otachi},
  title = {{A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25511},
}
Figure