用于确定哪些元素 N 和 M 与 N :M relation to keep, 的算法，可最大化结果对数

Question

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

一种可能的(远非最优的)“解决方案”是只保留那些提供所有菜肴的餐厅(导致保留的餐厅很少)，或者那些在所有餐厅都提供的菜肴(导致保留的菜肴很少)。但这不是我所追求的，因为我想确定进行此类选择的最佳方式，从而使餐厅和菜肴保持平衡。

我正在使用 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

首先，观察 Restaurants-to-Dishes 映射是 bipartite graph .接下来，观察“所有餐厅供应每道菜，所有菜肴都由每家餐厅供应”问题的任何解决方案都是完全二部子图，或 biclique。 .最后，由于您希望最大化菜肴-餐厅对的数量(而不是最大化包含菜肴的数量或参与餐厅的数量)，因此您尝试查找的 biclique 称为边最大值(另一个最大的 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 withApplication to the Integration of Diverse Biological Data Types

论文在第 4 页有伪代码。