traveling salesman problem 2

On the traveling salesman problem with neighborhoods : 

On the traveling salesman problem with neighborhoods With: Khaled Elbassioni Aleksei Fishkin Hans Bodlaender Corinne Feremans Alexander Grigoriev Eelko Penninkx Thomas Wolle

Euclidean Group TSP : 

Euclidean Group TSP Given n sets of points in the plane find a tour of minimum length tour that connects all sets.

TSP with neighborhoods : 

TSP with neighborhoods

TSP with neighborhoods : 

TSP with neighborhoods VLSI design

TSP with neighborhoods (discrete) : 

TSP with neighborhoods (discrete)

TSP with neighborhoods : 

TSP with neighborhoods Known: 2-ε inapproximability (Safra, Schwarz 2003) log n approximation (Mata, Mitchell 1995)

TSP with neighborhoods : 

TSP with neighborhoods Known: 2-ε inapproximability (Safra, Schwarz 2003) log n approximation (Mata, Mitchell 1995) O(1)-approx. for : fat regions (De Berg et al. 2005) fat objects (Elbassioni et al. 2005) lines (Dumitrescu, Mitchell 2003)

TSP with neighborhoods : 

TSP with neighborhoods Known: 2-ε inapproximability (Safra, Schwarz 2003) log n approximation (Mata, Mitchell 1995) O(1)-approx. for : fat regions (De Berg et al. 2005) fat objects (Elbassioni et al. 2005) lines (Dumitrescu, Mitchell 2003) PTAS for unit disks (Dumitrescu, Mitchell 2003) PTAS for fat objects (Mitchell 2007)

Group TSP (3ρ / 2 -approximation) : 

Group TSP (3ρ / 2 -approximation) Algorithm: Solve LP Round Apply Christofides’ algorithm on selected pointset. Each group contains at most ρ points.

Group TSP : 

Group TSP

Group TSP : 

Group TSP Algorithm: (3ρ / 2 -approximation) Solve LP-2: Apply Christofides’ algorithm on A.

Group TSP : 

Group TSP

Group TSP : 

Group TSP

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions Fatness α: MinD { Area(RO)/Area(D) | D has centre in region R and boundaries intersect} Examples D disk α =1/4 line α =0 halfspace α =1/2

Slide 15: 

Packing lemma: The length of the shortest path connecting k α-fat regions in R2 is at least , where δ is the diameter of the smallest region. O(1)-approximation for fat regions

Slide 16: 

Proof: Packing lemma: The length of the shortest path connecting k α-fat regions in R2 is at least , where δ is the diameter of the smallest region. If the centre of a disk with diameter follows the path T , then the total area covered is: at least times at most O(1)-approximation for fat regions □

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 1 Step 1: Order the regions by their diameter 2 3 4 5 6 7

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 1 Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points.

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 2 Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points.

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 3 Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points.

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 4 Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points.

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 5 Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points.

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 6 Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points.

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions 7 Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points.

O(1)-approximation for fat regions : 

O(1)-approximation for fat regions Step 1: Order the regions by their diameter Step 2: In each region pick the point that is nearest to the already chosen points. Step 3: Find a minimum tour on chosen points.

Analysis : 

Analysis How does it compare with the optimal TSP tour?

Slide 28: 

Path starts at region j and visits the next k regions in OPT. region j Analysis How does it compare with the optimal TSP tour?

Slide 29: 

xj : Connection cost of region j. xj The algorithms cost. Analysis region j

Slide 30: 

Analysis If k ≥ 3/α then |T_j| is at least the smallest diameter on the path T_j. Packing lemma: The length of the shortest path connecting k α-fat regions in R2 is at least , where δ is the diameter of the smallest region.

Slide 31: 

Consider some region j. Let region h have smallest diameter on path T_j.. If h=j then j Analysis If k ≥ 3/α then |T_j| is at least the smallest diameter on the path T_j. Packing lemma: The length of the shortest path connecting k α-fat regions in R2 is at least , where δ is the diameter of the smallest region. h

Slide 32: 

Consider some region j. Let region h have smallest diameter on path T_j.. If h = j, then Otherwise, j Analysis If k ≥ 3/α then |T_j| is at least the smallest diameter on the path T_j. Packing lemma: The length of the shortest path connecting k α-fat regions in R2 is at least , where δ is the diameter of the smallest region. h

Slide 33: 

Let be set of regions j for which . Analysis Length of constructed tree is at most

Slide 34: 

Let be set of regions j for which . Let be set of regions j for which Analysis Length of constructed tree is at most

Slide 35: 

Let be set of regions j for which . Let be set of regions j for which Analysis Length of constructed tree is at most

Slide 36: 

Let be set of regions j for which . Let be set of regions j for which Analysis Length of constructed tree is at most □

Higher dimensions : 

Higher dimensions

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete)

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete) TSP with neighborhoods (unit disks).

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete) TSP with neighborhoods (unit disks). Algorithm [Dumitrescu and Mitchell 2003]: - Find maximal independent set. - Connect through walk over bounderies.

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete) TSP with neighborhoods (unit disks). Algorithm [Dumitrescu and Mitchell 2003]: - Find maximal independent set. - Connect through walk over bounderies.

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete) Algorithm B

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete) Step 1: Compute minimum covering box X. Algorithm B

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete) Step 1: Compute minimum covering box X. Step 2: Find minimal hitting set P’ inside X. Algorithm B

Intersecting fat regions (discrete) : 

Intersecting fat regions (discrete) Step 1: Compute minimum covering box X. Step 2: Find minimal hitting set P’ inside X. Step 3: Compute a (1+e)-approximate TSP-tour on P’. Algorithm B

Minimum corridor connection problem : 

Minimum corridor connection problem room Open problem CCCG 2000: Given a rectilinear decomposition of a square, find the minimum tree along the edges that connects all sections.

Minimum corridor connection problem : 

Minimum corridor connection problem room Open problem CCCG 2000: Given a rectilinear decomposition of a square, find the minimum tree along the edges that connects all sections.

Minimum corridor connection problem : 

Minimum corridor connection problem room Open problem CCCG 2000: Given a rectilinear decomposition of a square, find the minimum tree along the edges that connects all sections. w(e) More general: Given a weighted planar graph, connect all faces.

Subexponential time exact algorithm : 

Subexponential time exact algorithm Lipton-Tarjan planar separator theorem: There exists a subset of size that cuts the graph roughly in half. -time algorithm

Graphs with small branchwidth : 

Graphs with small branchwidth Branch decomposition 1 2 3 5 6 4 1 2 3 4 5 6 G T

Graphs with small branchwidth : 

Graphs with small branchwidth Branch decomposition 1 2 3 5 6 4 1 2 3 4 5 6 e G T

Graphs with small branchwidth : 

Graphs with small branchwidth Branch decomposition 1 2 3 5 6 4 1 2 3 4 5 6 Example: - 2 vertices in middle set of e. - Width of decomposition is 2 (maximum over all e of T). Branchwidth of graph is minimum width over all decompositions. e G T

Graphs with small branchwidth : 

Graphs with small branchwidth Planar graphs: Sphere cut decomposition

Graphs with small branchwidth : 

Graphs with small branchwidth Planar graphs: Sphere cut decomposition Theorem [Seymour and Thomas (1994), Dorn et al. (2005)]: If a planar graph has branchwidth B, then a sphere cut branch decomposition of width B can be found in O(n3) time.

Graphs with small branchwidth : 

Graphs with small branchwidth Planar graphs: Sphere cut decomposition Theorem [Seymour and Thomas (1994), Dorn et al. (2005)]: If a planar graph has branchwidth B, then a sphere cut branch decomposition of width B can be found in O(n3) time. Theorem Given a planar graph of branch width B, the minimum corridor connection problem can be solved in O(n3 + 2O(B)) time.

Graphs with small branchwidth : 

Graphs with small branchwidth For each edge e and triple (S,R,X) we store the optimal cost of subproblem. S is a subset of the middle set of e R is equivalence relation on S X is set of faces inside that are connected. Size of table for one edge: 2O(B)

Graphs with small branchwidth : 

Graphs with small branchwidth For each edge e and triple (S,R,X) we store the optimal cost of subproblem. S is a subset of the middle set of e R is equivalence relation on S faces inside that are connected. Size of table for one edge: 2O(B) Given a sphere cut branch decomposition of width B, the optimal tree can be found by DP in time 2O(B).

Graphs with small branchwidth : 

Graphs with small branchwidth Corollary: The mcc can be solved in O(n3+2O(k)) time on k-outerplanar graphs Fact: k-outerplanar graphs have branchwidth at most 2k.

PTAS for equal sized rooms : 

PTAS for equal sized rooms room

PTAS for Euclidean TSP (Arora) : 

PTAS for Euclidean TSP (Arora) round the instance- build quad tree- restrict the instance futher by defining portals on the dissection lines- apply DP to restricted instance.

PTAS for Euclidean TSP (Arora) : 

PTAS for Euclidean TSP (Arora) round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance.

PTAS for Euclidean TSP (Arora) : 

PTAS for Euclidean TSP (Arora) round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance. level 0

PTAS for Euclidean TSP (Arora) : 

PTAS for Euclidean TSP (Arora) round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance. level 0 level 1

PTAS for Euclidean TSP (Arora) : 

PTAS for Euclidean TSP (Arora) round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance. level 0 level 1 level 2

PTAS for Euclidean TSP : 

PTAS for Euclidean TSP round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance. level 0 level 1 level 2 level 3

PTAS for Euclidean TSP : 

PTAS for Euclidean TSP round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance. m portals per side, m=O((log n) / c) use at most r portals per side for crossing. r = O(1/c)

PTAS for Euclidean TSP : 

PTAS for Euclidean TSP round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance. m portals per side, m=O((log n) / c) use at most r portals per side for crossing. r = O(1/c) size of table for one node: mO(r)f(r)

PTAS for Euclidean TSP : 

PTAS for Euclidean TSP round the instance- build quad tree- restrict the instance further by defining portals on the dissection lines- apply DP to restricted instance. m portals per side, m=O((log n) / c) use at most r portals per side for crossing. r = O(1/c) size of table for one node: mO(r)f(r) time to compute one entry: (mO(r)f(r))4 → running time: n (logn)O(1/c) # nodes in tree : n log n

PTAS for equal sized rooms : 

PTAS for equal sized rooms Adjusting Arora’s algorithm to the mcc problem: Assumption: - Each room contains q x q square, - Perimeter is at most tq for some constant t ≥ 4. Changes: - dissection curves i.o. lines

PTAS for equal sized rooms : 

PTAS for equal sized rooms Adjusting Arora’s algorithm to the mcc problem: Assumption: - Each room contains q x q square, - Perimeter is at most tq for some constant t ≥ 4. Changes: - dissection curves i.o. lines

PTAS for equal sized rooms : 

PTAS for equal sized rooms Adjusting Arora’s algorithm to the mcc problem: Assumption: - Each room contains q x q square, - Perimeter is at most tq for some constant t ≥ 4. Problems: - dissection curves i.o. lines

PTAS for equal sized rooms : 

PTAS for equal sized rooms Adjusting Arora’s algorithm to the mcc problem: Assumption: - Each room contains q x q square, - Perimeter is at most tq for some constant t ≥ 4. Problems: - dissection curves i.o. lines - crossing paths i.o. points

PTAS for equal sized rooms : 

PTAS for equal sized rooms Adjusting Arora’s algorithm to the mcc problem: Assumption: - Each room contains q x q square, - Perimeter is at most tq for some constant t ≥ 4. Problems: - dissection curves i.o. lines - crossing paths i.o. points - solution follows dissection curves portal dis. curve

PTAS for fat regions (Mitchell 2007) : 

PTAS for fat regions (Mitchell 2007)

PTAS for fat regions : 

PTAS for fat regions Step 1: Rounding Step 2: D.P.

PTAS for fat regions : 

PTAS for fat regions Step 1: Rounding # Lines = n / ε Error: O(n L ε / n) ≤ O(OPT/ε) L

PTAS for fat regions : 

PTAS for fat regions Step 2: D.P.

PTAS for fat regions : 

PTAS for fat regions Step 2: D.P. Fix m=O(1/ ε)

PTAS for fat regions : 

PTAS for fat regions Step 2: D.P. Fix m=O(1/ ε)

PTAS for Euclidean TSP (Mitchell) : 

PTAS for Euclidean TSP (Mitchell) Theorem Any set of segments L can be extended to a set L* such that L* is m-guillotine and |L*| ≤ (1+2√2 / m) |L| . m = 2

PTAS for Euclidean TSP (Mitchell) : 

PTAS for Euclidean TSP (Mitchell) Definitions a point is on the m-span of a line γ if …… a point is m-dark w.r.t. a line γ if ...... γ Lemma There is a line γ for which | m-spanγ |≤ | m-darkγ |.

PTAS for Euclidean TSP (Mitchell) : 

PTAS for Euclidean TSP (Mitchell) Charged for from below: Each point is charged at most once from each side. Each segment is charged at most 2√2 / m times its length.

PTAS for Euclidean TSP (Mitchell) : 

PTAS for Euclidean TSP (Mitchell) # sub problems: - O(n4) boxes 2m points per side f(m) ways to combine => O(n4n16m) subproblems.

PTAS for fat regions : 

PTAS for fat regions M-region span Lemma There is a line γ s.t. |m-spanγ | + |M-region spanγ| ≤ |m-darkγ| + |M-region darkγ|.

PTAS for fat regions : 

PTAS for fat regions Theorem Any set of segments L can be extended to a set L* such that L* is (m,M)-guillotine and |L*| ≤ (1+2√2 / m )|L| + C0 / M . C0 = O(D1+D2+ ... + Dn). (Di is diameter of region i).

PTAS for fat regions : 

PTAS for fat regions Lemma OPT = Ω(D1+D2+ ... + Dn-1) / log n. M = log n / ε , m = 1/ε , C0=O(log n OPT) , L=OPT |L*| ≤ (1+2√2 / m )|L| + C0 / M = (1+2√2 ε)OPT + log n OPT / (log n / ε) = OPT + 2√2 ε OPT + ε OPT. # subproblems: O(n4n64m) · 2(8M) = c·n O(1/ ε)

Some open problems : 

Some open problems TSP on line segments: Find O(1)-approximation. TSP for non-fat regions: Find O(1)-approximation. MCC for planar graphs Find O(1)-approximation. Group TSP Find O(log n)-approximation.