FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 |

«Abstract We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of ...»

-- [ Page 1 ] --

The Asymmetric Traveling Salesman Problem

on Graphs with Bounded Genus

Shayan Oveis Gharan∗ Amin Saberi∗


We give a constant factor approximation algorithm for the asymmetric traveling salesman

problem when the support graph of the solution of the Held-Karp linear programming relaxation

has bounded orientable genus.

1 Introduction

We present the first constant-factor approximation algorithm for the Asymmetric Traveling Salesman Problem (ATSP) for metrics defined by a weighted directed graph with a bounded orientable genus. This is a very natural special case: consider a metric obtained by shortest path distances in a city with one way streets and a constant number of bridges and underpasses.

The result is in fact more general: we can obtain constant factor approximation algorithms when the underlying graph of the fractional solution of the Held-Karp linear programming relaxation has bounded orientable genus. It is easy to see that this is a less strict condition. In fact, it is known that the corner points of the Held-Karp relaxation polytope define very sparse graphs [9] and in practice they often turn out to be planar.

Even though the symmetric version of this problem (STSP) has been studied extensively on Euclidean [1], planar [10, 2, 13] or low-genus metrics [6], to the best of our knowledge, this is the first result of this type for Asymmetric TSP. Our algorithm rounds the solution of the Held-Karp linear programming relaxation. Therefore, it also gives a constant upper bound on the integrality gap. It is worth noting that the best-known constructions that lower bound the integrality gap [5] are also planar.

Our result builds on a central lemma in Asadpour et al. [3] that shows for finding a constantfactor approximation algorithm for ATSP, it is sufficient to find a “thin” tree in the fractional solution. Roughly speaking, a tree is -thin with respect to a graph G, if it does not contain more than an -fraction of the edges of G across any cut.

On the other hand, our approach for finding a tree and establishing its thinness is quite different from Asadpour et al. [3]: the embedding of the graph and its geometric dual will be crucial in finding a tree and proving its thinness. In particular, we take advantage of the correspondence between the cutsets of the graph G and cycles of the dual graph G∗. If G∗ does not have any short cycles and all the edges of T are far apart in G∗, then T can not contain too many edges from any cut of G and therefore it is thin.

∗ Department of Management Science and Engineering, Stanford University, Stanford, CA 94305. Email:{shayan, saberi}@stanford.edu.

Thin trees were first defined in the graph embedding literature in an attemptto prove a notoriously difficult conjecture by Jaeger on the existence of certain nowhere-zero flows [7]. Our result on the existence of thin trees in graphs with bounded genus also proves a weaker version of Jaeger’s conjecture and essentially implies the main result of [18]. Furthermore, our algorithm and its proof is much simpler than the vertex splitting argument of [18] that needs extensive case analysis.

In the rest of this section, let us sketch the main steps of the algorithm and its analysis. The main result of the paper is to find a polynomial-time algorithm for finding an f (γ)/k-thin tree in a k-edge connected graph of genus γ. In order to that, we first show how to find such a tree if the dual of the graph has high girth. This is sufficient for planar graphs. The dual of every cutset in G is a cycle in G∗. Therefore if G is k-edge connected, G∗ has girth at least k. In graphs with genus even slightly bigger than one, high connectivity does not imply high dual girth. In fact, the dual of a graph with high edge connectivity can have several short cycles. In section 4, we show how to remove short cycles from G∗ without creating too many connected components in G. For doing this, we have to use “surgical” operations like cutting handles and adding topological disks to the surface. The reader interested in the algorithm for planar graphs can skip this section and reads sections 2,3, and 5.

In the last section, we make the connection between ATSP and thin trees concrete. We show that an algorithm that finds an O(1)/k-thin spanning tree in a k-edge connected graph gives a constant factor approximation algorithm for ATSP.

2 Preliminaries In the Asymmetric Traveling Salesman problem (ATSP), we are given a set V of n points and a cost function c : V × V → R+. The goal is to find the minimum cost tour that visits every vertex at least once. Since we can replace every arc (u, v) in the tour with the shortest path from u to v, we can assume c satisfies the triangle inequality.

In this paper, we refer to multi-graphs (graphs with loops and parallel edges) simply as graphs.

Let G(V, E) be a weighted undirected graph with cost function c(e), and F ⊆ E be a collection of edges. We define c(F) := e∈F c(e).

Definition 2.1 A subset F ⊆ E is α-thin with respect to G, if for each set U ⊂ V,

–  –  –

where F(U, U) and E(U, U) are respectively the sets of edges of F and E that are in the cut (U, U).

We say F is (α, σ)-thin with respect to G, if it is α-thin and c(F) ≤ σc(E).

Given an instance of ATSP corresponding to the cost function c : V × V → R+, we can obtain a lower bound on the optimum value by considering the following linear programming relaxation

defined on the complete bidirected graph with vertex set V:

–  –  –

where T(U, U) is the set of the edges of T that are in the cut (U, U). Also we say that T is (α, σ)-thin with respect to x, if it is α-thin and moreover it is possible to orient the edges of T into T∗ such that

–  –  –

2.1 Surfaces and graph embedding We also need to recall some of the concepts in topological graph theory. By a surface, we mean a compact connected 2-manifold without boundary. It is well known that all surfaces are classified into the sphere with γ handles (denoted by Sγ ) or the crosscaps (denoted by Nγ ) and are called orientable and non-orientable surfaces respectively. Throughout this paper by a surface we mean an orientable surface, and all the theorems have been proved for orientable surfaces.

In the above definition, γ represents the genus of the surface. An equivalent definition for the genus of an orientable surface is the maximum number of disjoint simple closed curve which can be cut from the orientable surface without disconnecting it.

An embedding of a graph G into a surface Σ, is a homeomorphism i : G → Σ of G into Σ. The orientable genus of a graph G is the minimum γ such that G has an embedding in Sγ. For example, planar graphs have genus zero.

Let G(V, E) be a graph embedded on a surface Σ. A set S ⊆ E on Σ is separating if Σ − S is disconnected; otherwise S is called non-separating. For instance, the definition of orientable genus implies that any set of γ(Σ) + 1 disjoint cycles of G is separating.

Suppose that we have embedded G on a surface Σ. The geometric dual of G on Σ, G∗, is defined similar to the planar graphs. Particularly, The vertices of G∗ correspond to the faces of G. The edges of G∗ are in bijective correspondence e → e∗ with the edges of G, and the edge e∗ joins the vertices corresponding to the faces containing e in G. For a more extensive discussion of embeddings of graphs in surfaces, see [15].

3 Constructing a thin-tree Let G(V, E) be a connected graph embedded on an orientable surface, and G∗ be its geometric dual.

The dual-girth of G, denoted by g∗ (G) is the length of the shortest cycle in G∗. The main result of this section is the following lemma.

–  –  –

We will prove this lemma in the rest of this section. First note that if g∗ = 1, the lemma holds for trivial reasons. Therefore, without loss of generality assume that g∗ 1. That implies that no face of G can have two copies of an edge. In particular, G does not have any cut edge.

Define the distance of two edges in a graph to be the closest distance between their endpoints.

Our most basic tool for establishing the thinness of a tree T in G is to relate it to the pairwise distance of its corresponding edges T∗ in G∗. If G∗ does not have any short cycles and all the edges of T∗ are far apart in G∗, then the tree can not contain too many edges from any cut. We will

establish that for any subset of edges:

Lemma 3.2 Let F be a set of edges in G and F∗ be the corresponding edges in the dual.

If for some m ≤ g∗ (G), the distance between each pair of edges in F∗ is at least m, then F is m -thin in G.

Proof: Consider a cut S = (U, U) in G. Let us start by showing that S∗ is a collection of edgedisjoint cycles C1, C2,..., Cl in G∗. This is because the number of edges from S∗ incident to a vertex in G∗ is equal to the intersection of S with its corresponding face in G and that is an even number.

Otherwise, either that face contains two copies of an edge of S, or one could find a path P in that face such that P ∩ S = ∅, while the endpoints of P are in different sides of the cut, which are both impossible.

Because the distance of each pair of edges in F∗ is at least m, F∗ can not have more than max(1, length(Ci )/m ) edges in Ci, for 1 ≤ i ≤ l. Therefore,

–  –  –

Note that the equality holds by the assumption length(Ci ) ≥ g∗ ≥ m. Thus the number of edges of F in the cut (U, U) is no more than |(U, U)|/m and F is a 1/m-thin.

Considering the above Lemma, our goal will be to find a set of edges in G∗ that are sufficiently far. We will do this by finding long threads iteratively and selecting one edge from each thread.

A thread in a graph G is a maximal subgraph of G which is

• a path whose internal vertices all have degree 2 in G and its endpoints have degree at least 2, or

• a cycle in which all vertices except possibly one have degree 2.

Let us start by showing the existence of long threads. That is a straightforward application of the result of Goddyn et al. [8].

Lemma 3.3 A graph with minimum degree 2 and girth g, embedded on a surface with genus γ has a thread of length at least g/α.

Algorithm 1 Finds a thin tree in a graph with large dual-girth Input: A connected graph G embedded on an orientable surface with genus γ, and its dual G∗ with girth g∗.

Output: A spanning tree T with thinness at least g∗ /2α.

1: F∗ ← ∅ 2: while there exists an edge in G∗ do Find a thread P of length at least g∗ /α in G∗.


Add the middle edge of P to F∗ and remove it from G∗.

If P is a cycle, define its middle edge 4:

to be the one with the maximum distance from the high-degree vertex.

Iteratively delete all the degree one vertices with their incident edges.


6: end while 7: return A spanning tree T ⊆ F, where F is the set of edges corresponding to F∗ in G.

–  –  –

Because of the above lemma, Algorithm 1 terminates in polynomial time. The algorithm has an equivalent description in terms of the original graph G. Roughly speaking, in each iteration, we find a collection of consecutive parallel edges, add the middle edge from that collection to F and contract the end points. The embedding is crucial for the execution of this procedure because it provides a notion of a middle edge, and the notion of consecutive parallel edges (parallel edges that form a face).

It is also worth noting that |F| may end up being bigger than |V(G)| − 1 in an execution of Algorithm 1. This is because a thread in G∗ may be equivalent to a collection of parallel loops. The next lemma immediately proves Lemma 3.1.

Lemma 3.4 The set F computed in Algorithm 1 is connected and spanning in G.

Furthermore, the pairwise distance of the edges of F∗ in G∗ is at most g∗ /2α.

Proof: For the proof of the first statement, consider a non-empty cut S = (U, U) in G, and let S∗ be its dual. As we argued in the proof of Lemma 3.2, S∗ is a collection of cycles. It is also easy to see that Algorithm 1 selects at least one edge from each cycle.

For the second statement, first observe that after adding an edge e to F∗, the algorithm immediately removes all the edges that are of distance less than g∗ /2α from e. This is because all these edges are a part of the thread and therefore they are deleted sequentially.

Furthermore, although each iteration of the while loop may increase the distance of some pairs of edges, it never increases the distance of two edges that are closer than g∗ /α. Therefore, the distance of any pairs of edges that are closer than g∗ /α remains the same until one of them is deleted.

4 Increasing the girth of dual graph Let G(V, E) be a planar graph and G∗ be its geometric dual. In the previous section we showed that the girth of G∗ plays an important role in finding a thin spanning tree in G. By Whitney’s theorem [17], S ⊆ E is a cutset (minimal cut) in a planar graph G if and only if S∗ is a cycle in G∗. Therefore, if G is planar and k-edge connected, the girth of G∗ will be at least k. Unfortunately, this relation does not hold for non-planar graphs as their dual may have very small cycles.

In the rest of this section we show that we can get rid of these small cycles by deleting their edges. Deleting these edges may result in making the graph disconnected. We will try to increase the girth as much as possible while creating only a small number of connected components.

Later, we will find a thin tree in every connected component and merge them into a spanning tree using an arbitrary set of edges from the original graph. Since the number of connected components is small, this is possible with only a small loss in the thinness of the final spanning tree. In fact, in √ the statement of Theorem 5.1, the O( γ) dependence of the thinness on the genus of the surface comes from the balance between the number of connected components at the end of the procedure with the girth of the final graph in Lemma 4.1.

–  –  –

Pages:   || 2 |

Similar works:

«Empirische Pädagogik 2009, 23 (4), 392-409 © Empirische Pädagogik 2009, 23 (4), 392-409 Zeitschrift zu Theorie und Praxis erziehungswissenschaftlicher Forschung Originalbeitrag Christian Imdorf Die betriebliche Verwertung von Schulzeugnissen bei der Ausbildungsstellenvergabe1 Zusammenfassung: Im Widerspruch zum öffentlichen Diskurs belegt die internationale Forschungslage, dass Schulqualifikationen bei der (Ausbildungs-)Stellenvergabe oft nur zweitrangig sind. Gleichwohl können...»

«DISS ETH Nr. 19320 DETERMINATION OF THE ACTIVE SITES IN SUPPORTED PLATINUM CATALYSTS BY MEANS OF X-RAY ABSORPTION AND EMISSION SPECTROSCOPY A dissertation submitted to ETH ZURICH for the degree of Doctor of Sciences presented by JAGDEEP SINGH Master of Technology, Indian Institute of Technology Roorkee 03.10.1983 citizen of India accepted on the recommendation of Prof. Dr. Jeroen A. van Bokhoven Prof. Alexander Wokaun Dr. Pieter Glatzel Table of contents Abstract Zusammenfassung Chapter 1:...»

«AUTO-TRADE SPECIAL RISK DISCLOSURE Options involve substantial risk and are not suitable for all investors. You should review the OPTIONS DISCLOSURE DOCUMENT and endeavor to understand the contents before you fund your account and engage in any trading activity. All option trading is based on speculation, whether it is the purchase of Call and Put options, or the naked selling of Call and Put options. SPECULATION by definition is a strategy that takes greater than average risk to achieve the...»

«sprachreise los angeles sprachreise los angeles Coches De Los Ángeles Si Es Más Barato Batimos El Precio. Si Es Más Barato Batimos El Precio. Ofertas Exclusivas En Los Ángeles Sprachreisen für Schüler | fhc-sprachreisen.de direkt am Meer in England u Florida mit täglichem Programm u. Betreuung Sprachreise Englisch Sprachreise inkl. Englisch Sprachreise inkl. Flug ab 519 EUR hier kostenlos anfragen! Los Angeles Billigflüge | Fluege.de Flug Tickets aller Airlines im Vergleich Flüge ab 19...»

«PROPOSAL – CNG Auto. Side Loader PROPOSAL Purchasing Agent City of Norman (date) Post Office Box 370 Norman, OK 73070 Purchasing Agent: The undersigned proposes to furnish the following equipment, f.o.b., Norman, Oklahoma, ready for immediate use with all the necessary parts and accessories needed for its operation, as follows: One (1) New and Unused 62,000 GVWR Truck Chassis with 24 Yard Automated Side Load Refuse Compactor The truck chassis and refuse bodies shall be delivered as a complete...»

«UNTERSUCHUNGEN ZU LEUKOZYTÄREN OBERFLÄCHENANTIGENEN UND DER BILDUNG VON IFN-g UND IL-4 BEI ZELLEN AUS DER BRONCHOALVEOLÄREN LAVAGEFLÜSSIGKEIT (BALF) VON PFERDEN MIT COB MANUELA FRANZ INAUGURAL-DISSERTATION zur Erlangung des Grades eines Dr. med. vet. beim Fachbereich Veterinärmedizin der Justus-Liebig-Universität Gießen édition scientifique VVB LAUFERSWEILER VERLAG Das Werk ist in allen seinen Teilen urheberrechtlich geschützt. Jede Verwertung ist ohne schriftliche Zustimmung des...»

«Save this Book to Read Tulips An Integrated Semester Course Lkg PDF eBook at our Online Library. Get Tulips An Integrated Semester Course Lkg PDF file for free from our online library TULIPS AN INTEGRATED SEMESTER COURSE LKG PDF Are you looking for tulips an integrated semester course lkg PDF?. If you are a reader who likes to download tulips an integrated semester course lkg Pdf to any kind of device,whether its your laptop, Kindle or iPhone, there are more options now than ever before....»

«4.12 PARKS AND RECREATION This section describes possible impacts and mitigation for the Plan Alternative and Options and the No Action Alternative on parks and recreation facilities in the plan area. Parks and recreation facilities reviewed for this section include a wide variety of open space areas, sports fields, trails, and water-oriented facilities. This section updates and follows the same impact analysis and general methodology used in the 1993 Final EIS. This analysis includes...»

«Hochschule für Angewandte Wissenschaften Hamburg Fakultät Life Sciences Studiengang Ökotrophologie Gesundheitliche Bewertung von Süßstoffen unter besonderer Schwerpunktsetzung auf Aspartam Bachelorarbeit vorgelegt von Franziska Saalfrank Matrikelnr.: 1980390 Hamburg am 16. August 2013 Betreuender Prüfer Prof. Dr. Michael Häusler (HAW Hamburg) Zweiter Prüfer Prof. Dr. Michael Hamm (HAW Hamburg) I Inhaltsverzeichnis I INHALTSVERZEICHNIS I Inhaltsverzeichnis II Abbildungsverzeichnis III...»

«The author describes Fielding GraduateUniversity's distributed learning model, unique scholar-practitioner, which is intendedfor adult students whose professional -,,• and personalbackgrounds are considered an integral part of their educationaland development process. PhD and EdD Degrees for Mid-Career Professionals: Fielding Graduate University Judith L. Kuipers Introduction The traditional eighteen to twenty-two-year-old full time undergraduate student residing on campus is a distinct...»

«Роскошь как объект исследования: разработка определения Luxury as a Research Object: Working Out a Definition Зинчак Е.В. преподаватель кафедры общего и стратегического менеджмента Национальный Исследовательский Университет Высшая Школа Экономики – Нижний Новгород elena.zinchak@gmail.com Zinchak E.V. Assistant...»

«DUAL VOTE: A NOVEL USER INTERFACE FOR E-VOTING SYSTEMS Damien MacNamara, Francis Carmody, Ted Scully, Ken Oakley, Elizabeth Quane Department of Information Technology, Limerick Institute of Technology, Moylish Park, Limerick, Ireland J. Paul Gibson Le département Logiciels-Réseaux (LOR) Telecom & Management SudParis, 9 rue Charles Fourier, 91011 Évry cedex, France ABSTRACT The authors present a novel e-Voting system called “Dual Vote”, which couples the strength of electronic voting with...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.