Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Layers and matroids for the traveling salesman’s paths

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • Contributors:
      Dpt of Computer Science [Cornell]; Cornell University [New York]; Optimisation Combinatoire (G-SCOP_OC ); Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP); Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]); University of Bonn; College of William and Mary [Williamsburg] (WM); ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011)
    • بيانات النشر:
      Elsevier BV, 2018.
    • الموضوع:
      2018
    • نبذة مختصرة :
      International audience; Gottschalk and Vygen proved that every solution of the well-known subtour elimination linear program for traveling salesman paths is a convex combination of a set of more and more restrictive "generalized Gao trees" of the underlying graph. In this paper we give a short proof of this, as a {\em layered} convex combination of bases of a sequence of more and more restrictive matroids. Our proof implies (via the matroid partition theorem) a strongly-polynomial combinatorial algorithm for finding this convex combination. This is a new connection of the TSP to matroids, offering also a new polyhedral insight.
    • ISSN:
      0167-6377
    • الرقم المعرف:
      10.1016/j.orl.2017.11.002
    • الرقم المعرف:
      10.1016/j.orl.2017.11.002⟩
    • Rights:
      OPEN
    • الرقم المعرف:
      edsair.doi.dedup.....1b39a5f19b0a8b2440ed3e95b5ae3033