國立虎尾科技大學 |

Approximation Algorithms and Hardness of Routing on Disjoint Paths.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Approximation Algorithms and Hardness of Routing on Disjoint Paths./
Author:	Kim, Hong Kyun.
Description:	1 online resource (154 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B.
Contained By:	Dissertation Abstracts International79-11B(E).
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9780438088078

Approximation Algorithms and Hardness of Routing on Disjoint Paths.
Kim, Hong Kyun.

Approximation Algorithms and Hardness of Routing on Disjoint Paths. - 1 online resource (154 pages)

Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B.

Thesis (Ph.D.)--The University of Chicago, 2018.

Includes bibliographical references

In the classical node-disjoint paths problem, one is given as input an n-vertex graph G and a collection M = {(s1,t1 ),...,(sk,tk)} of pairs of vertices of G called source-destination or demand pairs, and the goal is to find a maximum-cardinality set of pairwise vertex-disjoint paths connecting the demand pairs. While the node-disjoint paths problem is one of the most basic routing problems, there has been a wide gap in our understanding of its approximability status. Currently, the best upper bound of O(√n) is achieved by a simple, greedy algorithm, while until very recently, the best known hardness of approximation result was a O(log1/2--delta n) lower bound for any constant delta, under standard complexity assumptions. Even for special cases of the problem, including when the input graph G is constrained to be planar, and surprisingly, even when G is a square grid, no better upper bound was known, while only NP-hardness was known on the negative side.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780438088078Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Approximation Algorithms and Hardness of Routing on Disjoint Paths.
LDR:03861ntm a2200361Ki 4500 001 919185
005 20181116131021.5
006 m o u
007 cr mn||||a|a||
008 190606s2018 xx obm 000 0 eng d
020 $a 9780438088078
035 $a (MiAaPQ)AAI10809569
035 $a (MiAaPQ)uchicago:14352
035 $a AAI10809569
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Kim, Hong Kyun. $3 1193696
245 1 0 $a Approximation Algorithms and Hardness of Routing on Disjoint Paths.
264 0 $c 2018
300 $a 1 online resource (154 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B.
500 $a Advisers: Julia Chuzhoy; Laszlo Babai.
502 $a Thesis (Ph.D.)--The University of Chicago, 2018.
504 $a Includes bibliographical references
520 $a In the classical node-disjoint paths problem, one is given as input an n-vertex graph G and a collection M = {(s1,t1 ),...,(sk,tk)} of pairs of vertices of G called source-destination or demand pairs, and the goal is to find a maximum-cardinality set of pairwise vertex-disjoint paths connecting the demand pairs. While the node-disjoint paths problem is one of the most basic routing problems, there has been a wide gap in our understanding of its approximability status. Currently, the best upper bound of O(√n) is achieved by a simple, greedy algorithm, while until very recently, the best known hardness of approximation result was a O(log1/2--delta n) lower bound for any constant delta, under standard complexity assumptions. Even for special cases of the problem, including when the input graph G is constrained to be planar, and surprisingly, even when G is a square grid, no better upper bound was known, while only NP-hardness was known on the negative side.
520 $a This thesis studies the approximability of the node-disjoint paths problem and three of its special cases. The first part of the thesis presents approximation algorithms for the special cases of the problem. In the first chapter, we investigate when the input graph is constrained to be a square grid. We show an O(n1/4)-approximation algorithm for this case and extend the approximation algorithm to show that the same upper bound holds for the closely related edge-disjoint paths problem in wall graphs.
520 $a In the second chapter, we focus on two cases of node-disjoint paths when the input graph G is planar. In the first case, we assume that we are given a planar graph G embedded into a disc, where all of the terminals participating in the demand pairs lie on the boundary of the disc. In the second case, we assume that we are given a cylinder obtained by removing two disjoint, open discs from it. We assume that G can be embedded into the cylinder such that all source terminals lie on the boundary of one of the discs and all destination terminals on the boundary of the other. We present an O(log k)-approximation algorithm for both problems of routing node-disjoint paths on a disc and a cylinder.
520 $a The third chapter of the thesis presents an improved inapproximability result for the node-disjoint paths problem. We show that the problem is 2O(√log n)-hard to approximate, unless all problems in NP have deterministic, quasi-polynomial time algorithms. The result holds even when the underlying graph is a sub-graph of a grid with all sources of the demand pairs lying on the boundary of the outer face.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a The University of Chicago. $b Computer Science. $3 845504
773 0 $t Dissertation Abstracts International $g 79-11B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10809569 $z click for full text (PQDT)