决定保留哪些具有 N:M 关系的元素 N 和 M 的算法，从而最大化结果对数

Question

我有一堆元素，两个类 N 和 M 以多对多的方式相互关联。我们称它们为 'restaurants' 和 'dishes'。我想选择餐厅和菜肴，以产生尽可能多的餐厅-菜肴对。但是每家餐厅必须提供我保留的每道菜，每家餐厅必须提供每道菜。我该如何找到我应该踢掉哪些餐厅和菜肴？

一种可能（远非最优）"solution" 是只保留那些提供所有菜肴的餐厅（导致保留的餐厅很少），或者所有餐厅都提供的那些菜肴（导致很少的菜肴被保留）。但这不是我所追求的，因为我想确定做出这种选择的最佳方式，从而使餐厅和菜肴保持公平的平衡。

我在Python工作；如果它对任何人有帮助，这里有一些简单的代码可以生成我正在处理的多对多数据类型：

import numpy as np

# let a dish be identified by an integer between 0 and 100
dishes = np.arange(100)

restaurants = []
for k in range(30):
    # a restaurant will have multiple dishes
    # the amount of dishes will also vary per restaurant
    # e.g. between 10 and 100 here
    restaurants.append(
        np.random.choice(dishes,
            size=np.random.randint(10, 100),
            replace=False)
    )

Answer 1

首先，观察餐厅到菜肴的映射是 bipartite graph. Next, observe that any solution to "all restaurants serve every dish, and all dishes are served by every restaurant" problem is a complete bipartite subgraph, or a biclique。最后，由于您希望最大化菜肴-餐厅对的数量（而不是最大化包含的菜肴数量或参与餐厅的数量），您试图找到的 biclique 称为 edge maximum（另一个最大biclique称为顶点最大值）。

因此，问题可以正式重述如下：

Find an edge maximum biclique in a bipartite graph.

这个问题有一个在this paper中描述的快速算法：

Yun Zhang, Elissa J. Chesler and Michael A. Langston

On Finding Bicliques in Bipartite Graphs: a Novel Algorithm with Application to the Integration of Diverse Biological Data Types

论文第 4 页有伪代码。

决定保留哪些具有 N:M 关系的元素 N 和 M 的算法，从而最大化结果对数

Algorithm for deciding which elements N and M with N:M relation to keep, which maximize resulting number of pairs

algorithm

optimization

combinations

graph-theory

combinatorics