不相交的字符串集 - 最小化问题

Question

有两组，s1 和 s2，每组包含成对的字母。一对仅当字母顺序相同时才等同于另一对，因此它们本质上是字符串（长度为 2）。集合s1和s2不相交，都不为空，每对字母只出现一次。

这是两个集合的示例：

s1 = { ax, bx, cy, dy }
s2 = { ay, by, cx, dx }

(s1∪s2)中所有字母的集合称为sl。集合 sr 是您选择的一组字母，但必须是 sl 的子集。您的目标是定义从 sl 中的字母到 sr 中的字母的映射 m，当应用于 s1 和 s2 时，将生成集合s1' 和 s2'，它们也包含成对的字母并且也必须不相交。

最明显的 m 只是将每个字母映射到自身。在此示例中（如下所示），s1 等同于 s1'，而 s2 等同于 s2'（但给定任何其他 m，这不会是这样的）。

a -> a
b -> b
c -> c
d -> d
x -> x
y -> y

目标是构造 m，使 sr（映射右侧的字母集）的字母数量尽可能少。为此，您可以将 sl 中的多个字母映射到 sr 中的同一个字母。请注意，根据 s1 和 s2 以及 m，您可能会违反 s1' 和 s2' 必须不相交的规则。例如，将 sl 中的每个字母映射到 sr.

中的单个字母显然会违反该规则

那么，给定 s1 和 s2，有人如何构造一个 m 来最小化 sr，同时确保 s1' 和 s2' 不相交？

这是问题的简化可视化：

Answer 1

这个问题是 NP 难的，为了证明这一点，考虑减少这个问题的图形着色。

证明：设 G=(V,E) 为我们要为其计算最小 graph coloring 问题的图。形式上，我们要计算图形的色数，这是 G 可 k 着色的最低 k。

要将图形着色问题简化为此处描述的问题，请定义

 s1 = { zu : (u,v) \in E }
 s2 = { zv : (u,v) \in E }

其中 z 是除构造 s1 和 s2 之外未使用的魔法值。

通过以上集合的构造，对于任何映射m和任何边(u,v)我们必须有m(u) != m(v)，否则s1'和[=20的不相交=] 会被违反。因此，任何最优 sr 都是最优颜色集（z 除外），用于为图 G 着色，而 m 是定义为哪个节点分配哪种颜色的映射。 QED.

上面的证明可能会给人一种直觉，即研究图形着色近似值将是一个好的开始，而且确实可能会，但其中涉及一个混杂因素。这个混杂因素是，对于两个元素 ab \in s1 和 cd \in s2，如果 m(a) = m(c) 那么 m(b) != m(d)。从逻辑上讲，这等同于语句 m(a) != m(c) 或 m(b) != m(d)。这些类型的约束，孤立地，不会自然地映射到类似的图形问题（因为 or 语句。）

有多种方法可以将此问题表述为（二进制）ILP 并以此方式解决。与自定义设计和调整的分支定界实现相比，这可能会给您带来（稍微）差的结果（假设您想要找到最佳解决方案），但可以与交钥匙求解器一起使用。

如果您对近似值更感兴趣（可能具有保证的最优比率），我会研究针对您的问题的 SDP 放松和适当的舍入方案。这种水平的工作很可能是那种人们会投资于中小型研究论文的工作。

不相交的字符串集 - 最小化问题

Disjoint Sets of Strings - Minimization Problem

algorithm

set-theory

set

mathematical-optimization