论文标题
在有界属图上近似最大积分多量
Approximating maximum integral multiflows on bounded genus graphs
论文作者
论文摘要
我们设计了第一个恒定因子近似算法，用于在供应图和需求边缘的实例中找到最大总价值的整体多商品流，并可以将需求边缘嵌入到有界属的可定向表面上。这扩展了平面实例的最新结果。我们的技术包括一种无跨的算法，该算法比平面案例中要困难得多，在支持LP溶液中的循环中的一个分区中，将LP溶液支持到自由同型类别中，以及用于自由同型非分离循环的新舍入程序。
We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.
