English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In recent years, there has been much interest in phase transitions ofcombinatorial problems. Phase transitions have been successfully used toanalyze combinatorial optimization problems, characterize their typical-casefeatures and locate the hardest problem instances. In this paper, we studyphase transitions of the asymmetric Traveling Salesman Problem (ATSP), anNP-hard combinatorial optimization problem that has many real-worldapplications. Using random instances of up to 1,500 cities in which intercitydistances are uniformly distributed, we empirically show that many propertiesof the problem, including the optimal tour cost and backbone size, experiencesharp transitions as the precision of intercity distances increases across acritical value. Our experimental results on the costs of the ATSP tours andassignment problem agree with the theoretical result that the asymptotic costof assignment problem is pi ^2 /6 the number of cities goes to infinity. Inaddition, we show that the average computational cost of the well-knownbranch-and-bound subtour elimination algorithm for the problem also exhibits athrashing behavior, transitioning from easy to difficult as the distanceprecision increases. These results answer positively an open question regardingthe existence of phase transitions in the ATSP, and provide guidance on howdifficult ATSP problem instances should be generated.

Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem