计算机科学/离散数学研讨会2

图交叉数是一个被广泛研究和应用的基本问题。在这个问题中，目标是在平面上绘制一个输入图$G$，从而使其边缘图像之间的交叉次数最小化。这个问题是出了名的难，尽管做了大量的工作，但非平凡逼近算法只适用于有界度图。即使在这种特殊情况下，当前最好的算法实现$\tilde O(\sqrt{n})$-近似，而当前最好的负结果不排除常数因子近似。目前该问题的所有近似算法都建立在相同的范例上，这也被用于实践:计算一个边的集合$E'$(称为平面化集)，使得$G\ set- E'$是平面的;计算$G\ set- E'$的平面图;然后将E的边缘图添加到结果图中。不幸的是，有一些图$G$的例子，其中这种方法的任何实现都必须引起$\Omega(OPT^2)$交叉，其中OPT是最优解的值。这个障碍似乎注定了目前唯一已知的为该问题设计近似算法的方法，并阻止它产生比$\tilde O(\sqrt{n})$-逼近更好的方法。

我们提出了一种新的范式，使我们能够克服这一障碍。使用新的范式，我们将交叉数问题简化为旋转系统的交叉数问题-交叉数问题的一种变体，其中入射到每个顶点的边的顺序作为输入的一部分是固定的。然后，我们展示了这个新问题的随机算法，它允许我们在低次图上获得图交叉数的次多项式近似。

本次演讲基于与Julia Chuzhoy和Sepideh Mahabadi的合作。