Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximate the k-Set Packing Problem by Local Improvements   We study algorithms based on local improvements for the $k$-Set Packing
problem. The well-known local improvement algorithm by Hurkens and Schrijver
has been improved by Sviridenko and Ward from $\frac{k}{2}+\epsilon$ to
$\frac{k+2}{3}$, and by Cygan to $\frac{k+1}{3}+\epsilon$ for any $\epsilon>0$.
In this paper, we achieve the approximation ratio $\frac{k+1}{3}+\epsilon$ for
the $k$-Set Packing problem using a simple polynomial-time algorithm based on
the method by Sviridenko and Ward. With the same approximation guarantee, our
algorithm runs in time singly exponential in $\frac{1}{\epsilon^2}$, while the
running time of Cygan's algorithm is doubly exponential in
$\frac{1}{\epsilon}$. On the other hand, we construct an instance with locality
gap $\frac{k+1}{3}$ for any algorithm using local improvements of size
$O(n^{1/5})$, here $n$ is the total number of sets. Thus, our approximation
guarantee is optimal with respect to results achievable by algorithms based on
local improvements.

21
The categories of this paper are: adap-org
3
The categories of this paper are: physics
8
The categories of this paper are: hep-ex
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
14
The categories of this paper are: math-ph
20
The categories of this paper are: acc-phys
0
The categories of this paper are: hep-ph
19
The categories of this paper are: eess
28
The categories of this paper are: alg-geom
24
The categories of this paper are: dg-ga
22
The categories of this paper are: chao-dyn
18
The categories of this paper are: econ
27
The categories of this paper are: comp-gas
36
The categories of this paper are: cmp-lg
15
The categories of this paper are: nucl-ex