{
  "annotation_id": "2d23a372-3d73-4be0-908f-8c97b0ecfa3f",
  "date_created": "2026-02-17T05:53:19.848000Z",
  "date_modified": "2026-02-17T05:53:19.848000Z",
  "file_hash": "b5d25455cf08aa3d58ced526ecd0a764ac197e1b48c5af1f391dca59efdde018",
  "private": false,
  "record": {
    "abstract": "The \\emph{Tree Augmentation Problem (TAP)} is given a tree $T=(V,E_T)$ and additional set of {\\em links} $E$ on $V\\times V$, find $F \\subseteq E$ such that $T \\cup F$ is $2$-edge-connected, and $|F|$ is minimum. The problem is APX-hard \\cite{r} even in if links are only between leaves \\cite{r}. The best known approximation ratio for TAP is $1.393$, due to Traub and Zenklusen~\\cite{tr1} J.~ACM,~2025 using the {\\em relative greedy} technique \\cite{zel}.\n  \\noindent We introduce a new technique called the {\\em deferred local ratio technique}. In this technique, the disjointness of the local-ratio primal-dual type does not hold. The technique applies Set Cover problem under certain conditions (see Section \\ref{lr}). We use it provide a We use it to provide a $4/3$ approximation algorithm for TAP. It is possible this technique will find future applications.\n  The running time is The running time is $O(m\\cdot\\sqrt{n})$ time \\cite{vaz}, \\cite{vaz1}. Faster than \\cite{tr1} \\cite{LS}\n  and LP based algorithms as we do not enumeratestructures of size $exp(\\Theta(f(1/\\epsilon)\\cdot \\log n)).$ Nor do we scale and round.\n  \\noindent \\cite{ed} has an implementation \\cite{kol} that is extensively used in the industry.",
    "arxiv_id": "2601.09219",
    "authors": [
      "Guy Kortsarz"
    ],
    "categories": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "title": "A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing",
    "url": "https://arxiv.org/abs/2601.09219",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "10f0406a-ec64-4d9e-ad0a-41f3b7a39ed0",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}