000859646 001__ 859646
000859646 005__ 20240625095119.0
000859646 0247_ $$2doi$$a10.1103/PhysRevE.98.030101
000859646 0247_ $$2ISSN$$a1063-651X
000859646 0247_ $$2ISSN$$a1095-3787
000859646 0247_ $$2ISSN$$a1538-4519
000859646 0247_ $$2ISSN$$a1539-3755
000859646 0247_ $$2ISSN$$a1550-2376
000859646 0247_ $$2ISSN$$a2470-0045
000859646 0247_ $$2ISSN$$a2470-0053
000859646 0247_ $$2Handle$$a2128/21829
000859646 0247_ $$2WOS$$aWOS:000445970500001
000859646 0247_ $$2altmetric$$aaltmetric:44859077
000859646 037__ $$aFZJ-2019-00494
000859646 082__ $$a530
000859646 1001_ $$0P:(DE-Juel1)174546$$aCapelli, Riccardo$$b0$$eCorresponding author$$ufzj
000859646 245__ $$aExact value for the average optimal cost of the bipartite traveling salesman and two-factor problems in two dimensions
000859646 260__ $$aWoodbury, NY$$bInst.$$c2018
000859646 264_1 $$2Crossref$$3online$$bAmerican Physical Society (APS)$$c2018-09-27
000859646 264_1 $$2Crossref$$3print$$bAmerican Physical Society (APS)$$c2018-09-01
000859646 3367_ $$2DRIVER$$aarticle
000859646 3367_ $$2DataCite$$aOutput Types/Journal article
000859646 3367_ $$0PUB:(DE-HGF)16$$2PUB:(DE-HGF)$$aJournal Article$$bjournal$$mjournal$$s1552413443_13871
000859646 3367_ $$2BibTeX$$aARTICLE
000859646 3367_ $$2ORCID$$aJOURNAL_ARTICLE
000859646 3367_ $$00$$2EndNote$$aJournal Article
000859646 520__ $$aWe show that the average optimal cost for the traveling-salesman problem in two dimensions, which is the archetypal problem in combinatorial optimization, in the bipartite case, is simply related to the average optimal cost of the assignment problem with the same Euclidean, increasing, convex weights. In this way we extend a result already known in one dimension where exact solutions are avalaible. The recently determined average optimal cost for the assignment when the cost function is the square of the distance between the points provides therefore an exact prediction\overline{E_{N}} = \frac{1}{\pi} \log Nfor large number of points 2N. As a byproduct of our analysis also the loop covering problem has the same optimal average cost. We also explain why this result cannot be extended at higher dimensions. We numerically check the exact predictions.
000859646 536__ $$0G:(DE-HGF)POF3-899$$a899 - ohne Topic (POF3-899)$$cPOF3-899$$fPOF III$$x0
000859646 542__ $$2Crossref$$i2018-09-27$$uhttps://link.aps.org/licenses/aps-default-license
000859646 588__ $$aDataset connected to CrossRef
000859646 7001_ $$0P:(DE-HGF)0$$aCaracciolo, Sergio$$b1$$eCorresponding author
000859646 7001_ $$0P:(DE-HGF)0$$aDi Gioacchino, Andrea$$b2$$eCorresponding author
000859646 7001_ $$0P:(DE-HGF)0$$aMalatesta, Enrico M.$$b3$$eCorresponding author
000859646 77318 $$2Crossref$$3journal-article$$a10.1103/physreve.98.030101$$bAmerican Physical Society (APS)$$d2018-09-27$$n3$$p030101$$tPhysical Review E$$v98$$x2470-0045$$y2018
000859646 773__ $$0PERI:(DE-600)2844562-4$$a10.1103/PhysRevE.98.030101$$gVol. 98, no. 3, p. 030101$$n3$$p030101$$tPhysical review / E$$v98$$x2470-0045$$y2018
000859646 8564_ $$uhttps://juser.fz-juelich.de/record/859646/files/ETSP-Bipartito-2d.pdf$$yOpenAccess
000859646 8564_ $$uhttps://juser.fz-juelich.de/record/859646/files/PhysRevE.98.030101.pdf$$yOpenAccess
000859646 8564_ $$uhttps://juser.fz-juelich.de/record/859646/files/ETSP-Bipartito-2d.pdf?subformat=pdfa$$xpdfa$$yOpenAccess
000859646 8564_ $$uhttps://juser.fz-juelich.de/record/859646/files/PhysRevE.98.030101.pdf?subformat=pdfa$$xpdfa$$yOpenAccess
000859646 909CO $$ooai:juser.fz-juelich.de:859646$$pdnbdelivery$$pdriver$$pVDB$$popen_access$$popenaire
000859646 9101_ $$0I:(DE-588b)5008462-8$$6P:(DE-Juel1)174546$$aForschungszentrum Jülich$$b0$$kFZJ
000859646 9131_ $$0G:(DE-HGF)POF3-899$$1G:(DE-HGF)POF3-890$$2G:(DE-HGF)POF3-800$$3G:(DE-HGF)POF3$$4G:(DE-HGF)POF$$aDE-HGF$$bProgrammungebundene Forschung$$lohne Programm$$vohne Topic$$x0
000859646 9141_ $$y2019
000859646 915__ $$0StatID:(DE-HGF)0200$$2StatID$$aDBCoverage$$bSCOPUS
000859646 915__ $$0StatID:(DE-HGF)0600$$2StatID$$aDBCoverage$$bEbsco Academic Search
000859646 915__ $$0LIC:(DE-HGF)APS-112012$$2HGFVOC$$aAmerican Physical Society Transfer of Copyright Agreement
000859646 915__ $$0StatID:(DE-HGF)1150$$2StatID$$aDBCoverage$$bCurrent Contents - Physical, Chemical and Earth Sciences
000859646 915__ $$0StatID:(DE-HGF)0150$$2StatID$$aDBCoverage$$bWeb of Science Core Collection
000859646 915__ $$0StatID:(DE-HGF)0110$$2StatID$$aWoS$$bScience Citation Index
000859646 915__ $$0StatID:(DE-HGF)0111$$2StatID$$aWoS$$bScience Citation Index Expanded
000859646 915__ $$0StatID:(DE-HGF)9900$$2StatID$$aIF < 5
000859646 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000859646 915__ $$0StatID:(DE-HGF)0030$$2StatID$$aPeer Review$$bASC
000859646 915__ $$0StatID:(DE-HGF)0100$$2StatID$$aJCR$$bPHYS REV E : 2017
000859646 915__ $$0StatID:(DE-HGF)0300$$2StatID$$aDBCoverage$$bMedline
000859646 915__ $$0StatID:(DE-HGF)0199$$2StatID$$aDBCoverage$$bClarivate Analytics Master Journal List
000859646 920__ $$lno
000859646 9201_ $$0I:(DE-Juel1)IAS-5-20120330$$kIAS-5$$lComputational Biomedicine$$x0
000859646 9801_ $$aFullTexts
000859646 980__ $$ajournal
000859646 980__ $$aVDB
000859646 980__ $$aUNRESTRICTED
000859646 980__ $$aI:(DE-Juel1)IAS-5-20120330
000859646 981__ $$aI:(DE-Juel1)INM-9-20140121
000859646 999C5 $$1R. M. Karp$$2Crossref$$oR. M. Karp The Travelling Salesman Problem 1985$$tThe Travelling Salesman Problem$$y1985
000859646 999C5 $$1A. M. Frieze$$2Crossref$$oA. M. Frieze The Travelling Salesman Problem and its Variations 2002$$tThe Travelling Salesman Problem and its Variations$$y2002
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1126/science.220.4598.671
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1051/jphyslet:0198400450240114500
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1088/0305-4470/19/9/033
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1209/0295-5075/2/12/006
000859646 999C5 $$1M. Mézard$$2Crossref$$oM. Mézard Spin Glass Theory and Beyond: An Introduction to the Replica Method and its Applications 1987$$tSpin Glass Theory and Beyond: An Introduction to the Replica Method and its Applications$$y1987
000859646 999C5 $$1M. Mézard$$2Crossref$$9-- missing cx lookup --$$a10.1093/acprof:oso/9780198570837.001.0001$$y2009
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1051/jphyslet:019850046017076300
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1209/0295-5075/2/12/005
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1051/jphys:019860047080128500
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1209/0295-5075/8/3/002
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1017/S0305004100034095
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevLett.76.1188
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1051/jp1:1997129
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevE.97.052109
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1007/BF02579135
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevE.90.012118
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1088/1742-5468/2014/11/P11023
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1088/1742-5468/aad3f7
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevE.91.062125
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevLett.115.230601
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1007/s00440-018-0837-x
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1002/nav.3800020109
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1016/j.entcs.2011.06.003
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.4153/CJM-1965-045-4
000859646 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1137/1033004