AN APPROXIMATION ALGORITHM FOR FULLY PLANAR EDGE-DISJOINT PATHS

被引：3

作者：

Huang, Chien-Chung ^{[1
]}

Mari, Mathieu ^{[2
]}

Mathieu, Claire ^{[3
]}

Schewior, Kevin ^{[4
]}

Vygen, Jens ^{[5
]}

机构：

[1] Univ PSL, Ecole Normale Super, CNRS, F-75005 Paris, France

[2] Univ PSL, Comp Sci Dept, Ecole Normale Super, F-75005 Paris, France

[3] Univ Paris, CNRS, IRIF, F-75205 Paris, France

[4] Univ Cologne, Dept Math Informat, D-50931 Cologne, Germany

[5] Univ Bonn, Hausdorff Ctr Math, Res Inst Discrete Math, D-53113 Bonn, Germany

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2021年 / 35卷 / 02期

关键词：

approximation algorithm; edge-disjoint paths; planar graphs; ODD CYCLES; MULTICUT; FLOW; THEOREMS; HARDNESS; RATIO; CUTS;

D O I：

10.1137/20M1319401

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

引用

页码：752 / 769

页数：18

共 40 条

[1]

Andrews M., 2015, P 46 ANN IEEE S FDN, P226

[2]

[Anonymous], 2001, J HOPKINS STUD MATH

[3]

AUMANN Y, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P567

[4] Disjoint paths in sparse graphs [J].

Bentz, Cedric .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (17) :3558-3568

[5]

Chekuri C., 2006, THEORY COMPUT, V2, P137, DOI DOI 10.4086/T0C.2006.V002A007

[6] On the integrality ratio for TREE AUGMENTATION [J].

Cheriyan, J. ;

Karloff, H. ;

Khandekar, R. ;

Konemann, J. .

OPERATIONS RESEARCH LETTERS, 2008, 36 (04) :399-401

[7] Almost Polynomial Hardness of Node-Disjoint Paths in Grids [J].

Chuzhoy, Julia ;

Kim, David H. K. ;

Nimavat, Rachit .

STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, :1220-1233

[8] Improved Approximation for Node-Disjoint Paths in Planar Graphs [J].

Chuzhoy, Julia ;

Kim, David H. K. ;

Li, Shi .

STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, :556-569

[9] New Hardness Results for Routing on Disjoint Paths [J].

Chuzhoy, Julia ;

Kim, David H. K. ;

Nimavat, Rachit .

STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :86-99

[10]

Chuzhoy J, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P855

← 1 2 3 4 →