Polynomial-time approximation schemes for NP-hard geometric problems

Publish in

Documents

28 views

Please download to get full document.

View again

of 35
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Polynomial-time approximation schemes for NP-hard geometric problems. Reto Spöhel. TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: A A A A A. or. On Euclidean vehicle routing with allocation. Jan Remy, Reto Spöhel, Andreas Weißl
Transcript
Polynomial-time approximation schemes for NP-hard geometric problems Reto Spöhel TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: AAAAA or problems On Euclidean vehicle routing problemswith allocation Jan Remy, Reto Spöhel, Andreas Weißl (appeared in WADS ’07, CGTA ’11) TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: AAAAA The problemsTraveling Salesman Problem
  • The Traveling Salesman Problem (TSP)
  • Input: edge-weighted graph G
  • Output: Hamilton cycle in G with minimum edge-weight
  • Motivation:
  • Traveling salesman ;-)
  • Complexity:
  • NP-hard
  • Admits no constant factor approximation (unless P=NP) [Sahni and Gonzalez 76]
  • Metric TSP problems
  • Metric TSP
  • Input: edge-weighted graph G satisfying triangle inequality
  • Output: Hamilton cycle in G with minimum edge-weight
  • Motivation:
  • real-world problems usually satisfy triangle inequality
  • Complexity:
  • still NP-hard
  • admits 3/2-approximation [Christofides 76]
  • admits no PTAS (unless P=NP) [Aroraet al. 98]
  • Euclidean TSP problems
  • Euclidean TSP
  • Input: points P ½R2
  • Output: tour ¼ through P with minimal length
  • Complexity:
  • still NP-hard [Papadimitriou 77]
  • admits PTAS [Arora 96; Mitchell 96]
  • Euclidean TSP problems
  • Euclidean TSP
  • Input: points P ½R2
  • Output: tour ¼ through P with minimal length
  • Complexity:
  • still NP-hard [Papadimitriou 77]
  • admits PTAS [Arora 96; Mitchell 96]
  • …even one with complexity O(n log n).
  • Arora (FOCS ’97) There is a randomized PTAS for Euclidean TSP with complexityn logO(1/²) n. Rao, Smith (STOC ’98) There is a randomized PTAS for Euclidean TSP with complexityO(n log n). VRAP problems
  • (Euclidean) VehicleRoutingwithAllocation (VRAP)
  • Input: points P ½R2 , constant ¯¸ 1
  • Output: tour ¼ through subset T µ P minimizing
  • Motivation:
  • salesman does not visit all customers
  • customers not visited go to next tourpoint, which is more expensive by a factor of ¯.
  • VRAP problems
  • (Euclidean) VehicleRoutingwithAllocation (VRAP)
  • Input: points P ½R2 , constant ¯¸ 1
  • Output: tour ¼ through subset T µ P minimizing
  • Complexity:
  • NP-hard, since setting ¯¸ 2 yields Euclidean TSP
  • as forEuclidean TSP, thereexists a quasilinear PTAS
  • Remy, S., Weißl (WADS ’07) There is a randomized PTAS for VRAP with complexityO(n log4n). Steiner VRAP problems
  • Steiner VRAP
  • Input: points P ½R2 , constant ¯¸ 1
  • Output: subset T µ P, set of points S ½R2(Steiner Points), tour ¼ through T [ S minimizing
  • Motivation:
  • salesmanmay also stop en route to servecustomers
  • Steiner VRAP problems
  • Steiner VRAP
  • Input: points P ½R2 , constant ¯¸ 1
  • Output: subset T µ P, set of points S ½R2(Steiner Points), tour ¼ through T [ S minimizing …
  • Complexity:
  • NP-hard
  • admits PTAS
  • …even a quasilinear one
  • Armon, Avidor, Schwartz(ESA ’06) There is a randomized PTAS for Steiner VRAP with complexity nO(1/²). Remy, S., Weißl (WADS ’07) There is a randomized PTAS for Steiner VRAP with complexity n logO(1/²) n. Techniques problems
  • Finding a good solution for VRAP means
  • finding a good set of tour points T µ P
  • finding a good tour on this set T simultaneously.
  • a) is essentially a facility location problem.
  • We use the adaptive dissection technique, due to [Kolliopoulos and Rao, ESA ’99]
  • b) is Euclidean TSP.
  • We use dynamic programming on ‘patched short spanners’, due to [Rao and Smith, STOC ’98]
  • To put both ideas into perspective, we start by explaining the basics of dynamic programming in quadtrees, as introduced in [Arora, FOCS ’96] for Euclidean TSP
  • 3 2 1 Preliminaries problems
  • We assume that the input points P
  • have odd integer coordinates
  • lieinside a square whose sidelength is
  • a power of 2
  • of order O(n/²)
  • This is ok, since every (1+²/2)-approximation for the rescaled and shifted input P’ corresponds to a (1+²)-approximation for the original input P.
  • P Preliminaries problems
  • We assume that the input points P
  • have odd integer coordinates
  • lieinside a square whose sidelength is
  • a power of 2
  • of order O(n/²)
  • This is ok, since every (1+²/2)-approximation for the rescaled and shifted input P’ corresponds to a (1+²)-approximation for the original input P.
  • P’ Preliminaries problems
  • We assume that the input points P
  • have odd integer coordinates
  • lieinside a square whose sidelength is
  • a power of 2
  • of order O(n/²)
  • This is ok, since every (1+²/2)-approximation for the rescaled and shifted input P’ corresponds to a (1+²)-approximation for the original input P.
  • P’ Preliminaries problems
  • We assume that the input points P
  • have odd integer coordinates
  • lieinside a square whose sidelength is
  • a power of 2
  • of order O(n/²)
  • This is ok, since every (1+²/2)-approximation for the rescaled and shifted input P’ corresponds to a (1+²)-approximation for the original input P.
  • P Quadtrees problems
  • Choose origin of coordinate system (= center of large square) randomly.
  • thisistheonlysource of randomnessin all algorithms
  • Quadtrees problems
  • Split large square recursively into 4 smaller squares until squares have sidelength 2
  • Since bounding square has sidelength O(n), resulting tree has O(n2) nodes (squares) and depth O(log n)
  • Quadtrees problems
  • Truncatedquadtree: stop subdivision at empty squares
  • remaining tree has O(n log n) nodes
  • Portal-respecting solutions problems
  • Place O(log n/²) many equidistant points (‘portals’) on the boundary of each square.
  • Imposerestriction: Salesman may enter/leave a square only via its portals.
  • Lemma (Arora) In expectation, detouring all edges of the optimal salesmantour via the nearest portal increases its length only by a factor of 1+². Portal-respecting solutions problems
  • Place O(log n/²) many equidistant points (‘portals’) on the boundary of each square.
  • Imposerestriction: Salesman may enter/leave a square only via its portals.
  • Intuition: fortwofixedpoints:
  • good
  • Lemma (Arora) In expectation, detouring all edges of the optimal salesmantour via the nearest portal increases its length only by a factor of 1+². Portal-respecting solutions problems
  • Place O(log n/²) many equidistant points (‘portals’) on the boundary of each square.
  • Imposerestriction: Salesman may enter/leave a square only via its portals.
  • Intuition: fortwofixedpoints:
  • bad
  • butunlikely!
  • Lemma (Arora) In expectation, detouring all edges of the optimal salesmantour via the nearest portal increases its length only by a factor of 1+². Portal-respecting solutions problems
  • Place O(log n/²) many equidistant points (‘portals’) on the boundary of each square.
  • Imposerestriction: Salesman may enter/leave a square only via its portals.
  • i.e., thereis an expectednearly-optimalportal-respectingsalesman tour.
  • Wetry to find the best portal-respectingsalesman tour bydynamicprogramming in thequadtree.
  • Lemma (Arora) In expectation, detouring all edges of the optimal salesmantour via the nearest portal increases its length only by a factor of 1+². Dynamic programming in problemsquadtrees
  • For a given square Q, guess which portals are used bysalesman tour, and enumerate all possible configurations C.
  • For each configuration C, calculate estimate for the length of a good tour inside Q, subject to the restrictions given by C:
  • If Q is a leaf of the quadtree, by brute force.
  • If Q is an inner node of the quadtree, by recursing to its four children.
  • C Running time problems
  • Working in a non-truncated quadtree, we have to consider O(n2) squares. For each of these we have to consider2O(logn/²) = nO(1/²) configurations, and the estimate for each configuration can be calculated in time nO(1/²).
  • We obtain a PTAS with running time O(n2) ¢nO(1/²)¢nO(1/²)= nO(1/²)
  • This is essentially the technique used in the PTAS for Steiner VRAP by Armonet al.
  • Arora(FOCS ’96) Armon, Avidor, Schwartz(ESA ’06) There is a randomized PTAS for Euclidean TSP with complexity nO(1/²). There is a randomized PTAS for Steiner VRAP with complexity nO(1/²). Running time problems
  • Working in a non-truncated quadtree, we have to consider O(n2) squares. For each of these we have to consider2O(logn/²) = nO(1/²) configurations, and the estimate for each configuration can be calculated in time nO(1/²).
  • We obtain a PTAS with running time O(n2) ¢nO(1/²)¢nO(1/²)= nO(1/²)
  • to achieve quasilinear time, we can only use polylogarithmic time per square. In particular, we can only consider polylogarithmically many configurations per square.
  • Arora(FOCS ’96) There is a randomized PTAS for Euclidean TSP with complexity nO(1/²). Improving the running time problems Patching Lemma (Arora)
  • Idea: proceedbottom-upthroughquadtree and modifyeachsquarewithtoomanycrossingsbyintroducing line segments parallel to sides.
  • The optimal solution can be modified such that it crosses the boundary of every square at most O(1/²) many times.In expectation, this increases the length of the tour only by a factor of 1+².
  • The total length of thenew line segmentsisat most 3x
  •  modification on lowlevels of thequadtreearecheap.
  • x Improving the running time problems Patching Lemma (Arora)
  • i.e., thereis an expectednearly-optimalportal-respectingsalesman tour whichforeverysquareusesonly O(1/²) many of the O(log n) portals.
  • Looking for such a ‘patched’ solution, we only have to considerO(log n)O(1/²) =logO(1/²) n configurations per square!
  • The optimal solution can be modified such that it crosses the boundary of every square at most O(1/²) many times.In expectation, this increases the length of the tour only by a factor of 1+². Improving the running time problems Patching Lemma (Arora)
  • We only have to consider logO(1/²) n configurations per square.
  • Working in a truncatedquadtree, we obtain a PTAS with running time O(n log n) ¢logO(1/²) n ¢logO(1/²) n = n logO(1/²) n
  • The optimal solution can be modified such that it crosses the boundary of every square at most O(1/²) many times.In expectation, this increases the length of the tour only by a factor of 1+². Arora (FOCS ’97) There is a randomized PTAS for Euclidean TSP with complexityn logO(1/²) n. Improving the running time problems Patching Lemma (Arora)
  • Combiningtheextendedpatchinglemmawithstandardquadtreetechniquesforfacilitylocationproblems[Arora, Raghavan, Rao, STOC ’98], weobtain
  • The optimal solution can be modified such that it crosses the boundary of every square at most O(1/²) many times.In expectation, this increases the length of the tour only by a factor of 1+². Lemma The Patching Lemma extends to Steiner VRAP. Remy, S., Weißl (WADS ’07) There is a randomized PTAS for Steiner VRAP with complexity n logO(1/²) n. Improving the running time even further problems 2
  • Patchingrevisited:
  • In Arora’s technique, the ‘patching’ is not part of the algorithm – we simply know a nearly-optimal patched solution exists, and try to find it by dynamic programming.
  • Rao and Smith (STOC ’98) improved Arora’s running time by making the ‘patching’ part of the algorithm.
  • Effect: We only have to consider constantly many configurations per square!
  • Yields a PTAS with running time O(n log n) ¢O(1) ¢O(1)= O(n log n)
  • Rao, Smith (STOC ’98) There is a randomized PTAS for Euclidean TSP with complexityO(n log n). Improving the running time even further problems
  • Combinethe O(n log n) techniqueforEuclidean TSP with a clever techniqueforthefacilitylocationpart.
  • […]
  • Concludingremarks:
  • All algorithmscanbederandomizedtrivially at thecost of an extra factor O(n2).
  • All algorithmsgeneralize to higherdimensions (withincreased, but still polynomialrunningtimes).
  • 2 3 Remy, S., Weißl (WADS ’07) There is a randomized PTAS for (non-Steiner) VRAP with complexity O(nlog4n). Summary problems
  • VRAP is a combination of Euclidean TSP and a facilitylocationproblem.
  • Thetwostate-of-the-arttechniques
  • Dynamicprogramming on ‘patchedshortspanners’ (Rao and Smith, STOC ’98) for Euclidean TSP
  • Adaptive dissection(Kolliopoulos and Rao, ESA ’99) forfacilitylocation canbecombinedinto a O(n log4 n)-PTAS forVRAP.
  • Thank problemsyou!Questions?
    Related Search

    Previous Document

    Analisa4

    Next Document

    (2) bilik redaksi

    Related Documents
    No Time for Play
    Sep 21, 2017

    No Time for Play

    View more...
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks