2021-08-05T04:34:51Zhttps://tsukuba.repo.nii.ac.jp/oai
oai:tsukuba.repo.nii.ac.jp:000406192021-03-01T23:56:46Z
An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two小林, 佑輔Kawarabayashi, Ken-IchiKobayashi, Yusuke© ACM 2016. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM transactions on algorithms.vol.13,no.1,p.1,2016, http://dx.doi.org/10.1145/2960410.In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r-approximation algorithm for this problem is a polynomial-time algorithm that finds at least OPT/r edge-disjoint paths, where OPT denotes the maximum possible number of pairs that can be routed in a given instance. For a long time, an O(n½-approximation algorithm has been best known for this problem even if a congestion of two is allowed, that is, each edge is allowed to be used in at most two of the paths. In this article, we give a randomized O(n&frac;37 ċ poly(log n))-approximation algorithm with congestion two. This is the first result that breaks the O(n½)-approximation algorithm. In particular, we prove the following:\n\n(1) If we have a (randomized) polynomial-time algorithm for finding Ω(OPT&frac1p /polylog(n)) edge-disjoint paths for some p > 1, then we can give a randomized O(n½-α)-approximation algorithm for the edge-disjoint paths problem by using Rao-Zhou’s algorithm for some α > 0.\n\n(2) Based on the Chekuri-Khanna-Shepherd well-linked decomposition, we show that there is a randomized algorithm for finding Ω(OPT¼ /(log n)&frac32;) edge-disjoint paths connecting given terminal pairs with congestion two.\n\nOur framework for this algorithm is more general in the following sense. Indeed, the above two ingredients also work for the maximum edge-disjoint paths problem (with congestion one) if there is a (randomized) polynomial-time algorithm for finding Ω(OPT&frac;1p) edge-disjoint paths connecting given terminal pairs for some p > 1.Association Computing Machinery2016-12engjournal articlehttp://hdl.handle.net/2241/00145572https://tsukuba.repo.nii.ac.jp/records/4061910.1145/29604101549-6325AA12062871ACM transactions on algorithms131117https://tsukuba.repo.nii.ac.jp/record/40619/files/ATA_13-1.pdfapplication/pdf153.0 kB2017-03-17