Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximating Spanners and Directed Steiner Forest: Upper and Lower
  Bounds   It was recently found that there are very close connections between the
existence of additive spanners (subgraphs where all distances are preserved up
to an additive stretch), distance preservers (subgraphs in which demand pairs
have their distance preserved exactly), and pairwise spanners (subgraphs in
which demand pairs have their distance preserved up to a multiplicative or
additive stretch) [Abboud-Godwin SODA '16, Godwin-Williams SODA '16]. We study
these problems from an optimization point of view, where rather than studying
the existence of extremal instances we are given an instance and are asked to
find the sparsest possible spanner/preserver. We give an $O(n^{3/5 +
\epsilon})$-approximation for distance preservers and pairwise spanners (for
arbitrary constant $\epsilon > 0$). This is the first nontrivial upper bound
for either problem, both of which are known to be as hard to approximate as
Label Cover. We also prove Label Cover hardness for approximating additive
spanners, even for the cases of additive 1 stretch (where one might expect a
polylogarithmic approximation, since the related multiplicative 2-spanner
problem admits an $O(\log n)$-approximation) and additive polylogarithmic
stretch (where the related multiplicative spanner problem has an
$O(1)$-approximation).
  Interestingly, the techniques we use in our approximation algorithm extend
beyond distance-based problem to pure connectivity network design problems. In
particular, our techniques allow us to give an $O(n^{3/5 +
\epsilon})$-approximation for the Directed Steiner Forest problem (for
arbitrary constant $\epsilon > 0$) when all edges have uniform costs, improving
the previous best $O(n^{2/3 + \epsilon})$-approximation due to Berman et
al.~[ICALP '11] (which holds for general edge costs).

2
The categories of this paper are: math
26
The categories of this paper are: bayes-an
6
The categories of this paper are: astro-ph
25
The categories of this paper are: patt-sol
36
The categories of this paper are: cmp-lg
24
The categories of this paper are: dg-ga
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th
28
The categories of this paper are: alg-geom
21
The categories of this paper are: adap-org
27
The categories of this paper are: comp-gas
13
The categories of this paper are: quant-ph
8
The categories of this paper are: hep-ex
33
The categories of this paper are: plasm-ph
17
The categories of this paper are: q-fin
37
The categories of this paper are: supr-con