nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)

verfasst von : Abdullah Makkeh, Mozhgan Pourmoradnasseri, Dirk Oliver Theis

Erschienen in: Algorithms and Discrete Applied Mathematics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Graphs (1-skeletons) of Traveling-Salesman-related polytopes have attracted a lot of attention. Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes (Arthanari 2000) whose graphs contain the TSP polytope graphs as spanning subgraphs (Arthanari 2013). Unlike TSP polytopes, Pedigree polytopes are not “symmetric”, e.g., their graphs are not vertex transitive, not even regular.

We show that in the graph of the pedigree polytope, the quotient minimum degree over number of vertices tends to 1 as the number of cities tends to infinity.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Exact and Parameterized Algorithms for (k, i)-Coloring

Nächstes Kapitel Induced Matching in Some Subclasses of Bipartite Graphs

We speak of vertices of the pedigree graph and nodes of the cycles, to limit confusion.

The reason why we use this notion of “infinite cycle” is pure convenience. It does not add complexity, but it makes many of statements and proofs less cumbersome. Indeed, instead of an infinite cycle, it is ok to just use a cycle whose length M is longer than all the lengths occuring in the particular argument. So instead of “let A be an infinite cycle, and consider \(A_k\), \(A_\ell \), \(A_n\)” you have to say “let M be a large enough integer, \(A_M\) a cycle of length M, and \(A_k\), \(A_\ell \), \(A_n\) sub-cycles of \(A_M\)”. All the little arguments (e.g., Fact 8 below) have to be done in the same way.

Aguilera, N., Katz, R., Tolomei, P.: Vertex adjacencies in the set covering polyhedron. arXiv preprint arXiv:1406.6015 (2014)

Arthanari, T.S.: On pedigree polytopes and hamiltonian cycles. Discret. Math. 306, 1474–1792 (2006)MathSciNetCrossRefMATH

Arthanari, T.S.: Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope. Discret. Optim. 10(3), 224–232 (2013). http://dx.doi.org/10.1016/j.disopt.2013.07.001 MathSciNetCrossRef

Arthanari, T.S., Usha, M.: An alternate formulation of the symmetric traveling salesman problem and its properties. Discret. Appl. Math. 98(3), 173–190 (2000)MathSciNetCrossRefMATH

Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.O.: Combinatorial bounds on nonnegative rank and extended formulations. Discret. Math. 313(1), 67–83 (2013)MathSciNetCrossRefMATH

Grötschel, M., Padberg, M.W.: Polyhedral theory. In: Lawler, E.L., Lenstra, J.K., Kan, A., Shmoys, D.B. (eds.) The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, chap. 8, pp. 251–306. Wiley (1985)

Kaibel, V.: Low-dimensional faces of random 0/1-polytopes. In: Bienstock, D., Nemhauser, G. (eds.) IPCO 2004. LNCS, vol. 3064, pp. 401–415. Springer, Heidelberg (2004). doi:10.1007/978-3-540-25960-2_30 CrossRef

Kaibel, V., Pashkovich, K., Theis, D.O.: Symmetry matters for sizes of extended formulations. SIAM J. Discret. Math. 26(3), 1361–1382 (2012)MathSciNetCrossRefMATH

Kaibel, V., Remshagen, A.: On the graph-density of random 0/1-polytopes. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) APPROX/RANDOM -2003. LNCS, vol. 2764, pp. 318–328. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45198-3_27

10.

Makkeh, A., Pourmoradnasseri, M., Theis, D.O.: On the graph of the pedigree polytope. arXiv:1611.08431 (2016)

11.

Maksimenko, A.: The common face of some 0/1-polytopes with NP-complete non-adjacency relation. J. Math. Sci. 203(6), 823–832 (2014)MathSciNetCrossRefMATH

12.

Naddef, D.: Pancyclic properties of the graph of some 0–1 polyhedra. J. Comb. Theor. Ser. B 37(1), 10–26 (1984)MathSciNetCrossRefMATH

13.

Naddef, D.J., Pulleyblank, W.R.: The graphical relaxation: a new framework for the symmetric traveling salesman polytope. Math. Program. Ser. A 58(1), 53–88 (1993). http://dx.doi.org/10.1007/BF01581259 MathSciNetCrossRefMATH

14.

Naddef, D.J., Pulleyblank, W.R.: Hamiltonicity in (0–1)-polyhedra. J. Comb. Theor. Ser. B 37(1), 41–52 (1984)MathSciNetCrossRefMATH

15.

Oswald, M., Reinelt, G., Theis, D.O.: On the graphical relaxation of the symmetric traveling salesman polytope. Math. Program. Ser. B 110(1), 175–193 (2007). http://dx.doi.org/10.1007/s10107-006-0060-x MathSciNetCrossRefMATH

16.

Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-complete. Math. Program. 14(1), 312–324 (1978)MathSciNetCrossRefMATH

17.

Pashkovich, K., Weltge, S.: Hidden vertices in extensions of polytopes. Oper. Res. Lett. 43(2), 161–164 (2015)MathSciNetCrossRef

18.

Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383–412 (2012)MathSciNetCrossRefMATH

19.

Sarangarajan, A.: A lower bound for adjacencies on the traveling salesman polytope. SIAM J. Discret. Math. 10(3), 431–435 (1997)MathSciNetCrossRefMATH

20.

Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)MATH

21.

Sierksma, G.: The skeleton of the symmetric traveling salesman polytope. Discret. Appl. Math. 43(1), 63–74 (1993)MathSciNetCrossRefMATH

22.

Sierksma, G., Teunter, R.H.: Partial monotonizations of hamiltonian cycle polytopes: dimensions and diameters. Discret. Appl. Math. 105(1), 173–182 (2000)MathSciNetCrossRefMATH

23.

Theis, D.O.: A note on the relationship between the graphical traveling salesman polyhedron, the symmetric traveling salesman polytope, and the metric cone. Discret. Appl. Math. 158(10), 1118–1120 (2010). http://dx.doi.org/10.1016/j.dam.2010.03.003 MathSciNetCrossRefMATH

24.

Theis, D.O.: On the facial structure of symmetric and graphical traveling salesman polyhedra. Discret. Optim. 12, 10–25 (2014). http://www.sciencedirect.com/science/article/pii/S1572528613000625 MathSciNetCrossRefMATH

Titel: The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
verfasst von: Abdullah Makkeh
Mozhgan Pourmoradnasseri
Dirk Oliver Theis
Verlag: Springer International Publishing
Buch: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-319-53006-2

Electronic ISBN: 978-3-319-53007-9

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-53007-9_26

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner