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

We consider the following question. We are given a dense digraph $D_0$ withminimum in- and out-degree at least $\alpha n$, where $\alpha>0$ is a constant.We then add random edges $R$ to $D_0$ to create a digraph $D$. Here an edge $e$is placed independently into $R$ with probability $n^{-\epsilon}$ where$\epsilon>0$ is a small positive constant. The edges of $D$ are given edgecosts $C(e),e\in E(D)$, where $C(e)$ is an independent copy of the exponentialmean one random variable $EXP(1)$ i.e. $\Pr(EXP(1)\geq x)=e^{-x}$. Let$C(i,j),i,j\in[n]$ be the associated $n\times n$ cost matrix where$C(i,j)=\infty$ if $(i,j)\notin E(D)$. We show that w.h.p. the patchingalgorithm of Karp finds a tour for the asymmetric traveling salesperson problemthat is asymptotically equal to that of the associated assignment problem.Karp's algorithm runs in polynomial time.

Karp's patching algorithm on random perturbations of dense digraphs