The Limits of Local Search for Weighted k-Set Packing

Abstract

We consider the weighted k-Set Packing Problem, where, given a collection $\mathcal {S}$ of sets, each of cardinality at most k, and a positive weight function $w:\mathcal {S}\rightarrow \mathbb {R}_{>0}$, the task is to find a sub-collection of $\mathcal {S}$ consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time $o(\frac{k}{\log k})$-approximation unless $P=NP$ [11], most previous approaches rely on local search. For twenty years, Berman’s algorithm SquareImp [2], which yields a polynomial-time $\frac{k+1}{2}+\epsilon$-approximation for any fixed $\epsilon >0$, has remained unchallenged. Only recently, it could be improved to $\frac{k+1}{2}-\frac{1}{63,700,992}+\epsilon$ by Neuwohner [16]. In her paper, she showed that instances for which the analysis of SquareImp is almost tight are "close to unweighted" in a certain sense. But for the unit weight variant, the best known approximation guarantee is $\frac{k+1}{3}+\epsilon$. Using this observation as a starting point, we conduct a more in-depth analysis of close-to-tight instances of SquareImp. This finally allows us to generalize techniques used in the unweighted case to the weighted setting. In doing so, we obtain approximation guarantees of $\frac{k+\epsilon _k}{2}$, where $\lim _{k\rightarrow \infty } \epsilon _k = 0$. On the other hand, we prove that this is asymptotically best possible in that searching for local improvements of logarithmically bounded size cannot produce an approximation ratio below $\frac{k}{2}$.

1 Introduction

For a positive integer k, the weighted k-Set Packing Problem is defined as follows: Given a family $\mathcal {S}$ of sets each of size at most k together with a positive weight function $w:\mathcal {S}\rightarrow \mathbb {R}_{>0}$, the task is to find a sub-collection A of $\mathcal {S}$ of maximum weight such that the sets in A are pairwise disjoint. For $k\le 2$, the weighted k-Set Packing Problem reduces to the maximum weight matching problem, which can be solved in polynomial time [7]. However, as soon as $k\ge 3$, weighted k-Set Packing becomes NP-hard since it generalizes the optimization variant of the NP-complete 3-dimensional-matching problem [13]. Even more, Hazan, Safra and Schwartz [11] have shown that there cannot be a polynomial-time $o\left( \frac{k}{\log k}\right)$-approximation for weighted k-Set Packing unless $P=NP$.

On the positive side, a simple greedy algorithm yields an approximation guarantee of k. In order to improve on this, the technique that has proven most successful so far is local search. The basic idea is to start with an arbitrary solution (e.g. the empty one) and to iteratively improve the current solution by applying some sort of local modifications until no more of these exist. More precisely, given a feasible solution A to the weighted k-Set Packing problem, we call a collection $X\subseteq \mathcal {S}\setminus A$ consisting of pairwise disjoint sets a local improvement of A of size |X| if $w(X)>w(\{a\in A:\exists x\in X: a\cap x\ne \emptyset \}),$ that is, if replacing the collection of sets in A that intersect sets in X by the sets in X increases the weight of the solution. Note that whenever A is sub-optimum and $A^*$ is a solution of maximum weight, then $A^*\setminus A$ defines a local improvement of A. However, if one aims at designing a polynomial-time algorithm, it is of course infeasible to check subsets of $\mathcal {S}$ of arbitrarily large size.

1.1 The Unit Weight Case

For the special case of unit weights, Hurkens and Schrijver [12] showed that searching for local improvements of arbitrary large, but constant size results in approximation guarantees arbitrarily close to $\frac{k}{2}$. Their paper also provides matching lower bound examples proving their result to be tight. Since then, a lot of progress has been made regarding the special case where $w\equiv 1$, which we will also refer to as the unweighted k-Set Packing Problem. In 1995, at the cost of a quasi-polynomial running time, Halldórsson [10] achieved an approximation factor of $\frac{k+2}{3}$ by applying local improvements of size logarithmic in the total number of sets. Cygan, Grandoni and Mastrolilli [6] managed to get down to an approximation factor of $\frac{k+1}{3}+\epsilon$, still with a quasi-polynomial running time.

The first polynomial-time algorithm improving on the result by Hurkens and Schrijver [12] was obtained by Sviridenko and Ward [19] in 2013. By combining means of color coding with the algorithm presented in [10], they achieved an approximation ratio of $\frac{k+2}{3}$. This result was further improved to $\frac{k+1}{3}+\epsilon$ for any fixed $\epsilon >0$ by Cygan [5], obtaining a polynomial running time doubly exponential in $\frac{1}{\epsilon }$. The best approximation algorithm for the unweighted k-Set Packing Problem in terms of performance ratio and running time is due to Fürer and Yu [9] from 2014. They achieve the same approximation guarantee as Cygan [5], but a running time only singly exponential in $\frac{1}{\epsilon ^2}$. Moreover, they show that their result is best possible in that there exist arbitrarily large instances that feature solutions that do not permit any local improvement of size $o(|\mathcal {S}|^{\frac{1}{5}})$, but that are by a factor of $\frac{k+1}{3}$ smaller than the optimum.

1.2 General Weights and the MWIS in d-Claw Free Graphs

In the weighted setting, much less is known. Arkin and Hassin [1] have shown that unlike the unit weight case, searching for local improvements of constant size cannot produce an approximation ratio better than $k-1$ for general weights. Both papers improving on this deal with a more general problem, the Maximum Weight Independent Set Problem (MWIS) in $k+1$-claw free graphs [2, 4]:

Fig. 1.

A d-claw C for $d=3$.

For $d\ge 1$, a d-claw C [2] is defined to be a star consisting of one center node and a set $T_C$ of d talons connected to it (see Fig. 1). An undirected graph $G=(V,E)$ is said to be d-claw free if none of its induced sub-graphs forms a d-claw. For $d\le 3$, the MWIS in d-claw free graphs can be solved in polynomial time (see [14, 18] for the unweighted, [15] for the weighted variant), while for $d\ge 4$, again no $o(\frac{d}{\log d})$-approximation algorithm is possible unless $P=NP$ [11].

If we define an independent set $X\subseteq V\setminus A$ to be a local improvement of A if the weight of X exceeds the weight of its neighborhood in A, then most of the previous results for the (weighted or unweighted) k-Set Packing Problem also apply to the more general context of the MWIS in $k+1$-claw free graphs. However, it is not known how to get down to a polynomial (instead of quasi-polynomial) running time for the algorithms in [5, 19] and [9] since there is no obvious equivalent to coloring the underlying universe.

By considering the conflict graph $G_\mathcal {S}$ associated with an instance of weighted k-Set Packing, one obtains a weight preserving one-to-one correspondence between feasible solutions to the k-Set Packing Problem and independent sets in $G_\mathcal {S}$. The vertices of $G_\mathcal {S}$ are given by the sets in $\mathcal {S}$ and the edges represent non-empty set intersections. It is not hard to see that $G_\mathcal {S}$ is $k+1$-claw free.

The first significant improvement over the approximation guarantee of $d-1$ achieved by the greedy approach for the MWIS in d-claw free graphs was made by Chandra and Halldórsson [4]. In each iteration, their algorithm BestImp picks a certain type of local improvement that maximizes the ratio between the total weight of the vertices added to and removed from the current solution. By further scaling and truncating the weight function to ensure a polynomial number of iterations, Chandra and Halldórsson [4] obtain a $\frac{2d}{3}+\epsilon$-approximation algorithm for the MWIS in d-claw free graphs.

1.3 Berman’s Algorithm SquareImp

For 20 years, Berman’s algorithm SquareImp [2] has been the state-of-the-art for both the MWIS in d-claw free graphs and weighted k-Set Packing. SquareImp proceeds by iteratively applying local improvements of the squared weight function that arise as sets of talons of claws in G, until no more exist. In doing so, SquareImp achieves an approximation ratio of $\frac{d}{2}$, leading to a polynomial-time $\frac{d}{2}+\epsilon$-approximation algorithm for the MWIS in d-claw free graphs for any fixed $\epsilon >0$ (and a $\frac{k+1}{2}+\epsilon$-approximation for weighted k-Set Packing).

Berman [2] also provides an example for $w\equiv 1$ showing that his analysis is tight. As the example uses unit weights, he concludes that applying the same type of local improvement algorithm for a different power of the weight function does not provide further improvements. However, as also implied by the result in [12], while no small improvements forming the set of talons of a claw in the input graph exist in the tight example given by Berman [2], once this additional condition is dropped, improvements of small constant size can be found quite easily. This observation is the basis of a recent paper by Neuwohner [16], who managed to obtain an approximation guarantee slightly below $\frac{d}{2}$ by taking into account a broader class of local improvements, namely all improvements of the squared weight function of size at most $(d-1)^2+(d-1)$.

2 Our Contribution

In this paper, we revisit the analysis of the algorithm SquareImp proposed by Berman [2]. Following [16], we show that whenever the analysis is close to being tight, the instance is locally unweighted in the sense that almost every time when a vertex from the solution chosen by SquareImp and a vertex from any optimum solution share an edge, their weights must be very similar. While [16] merely focuses on one of the two major steps in Berman’s analysis, we consider both of them, allowing us to derive much stronger statements concerning the structure of instances where SquareImp does not do much better than a $\frac{d}{2}$-approximation. In particular, we are able to transfer techniques that are used in the state-of-the-art works on the unweighted k-Set Packing Problem [5, 9] to a setting where vertex weights are locally similar. This is the main ingredient for our algorithm LogImp. In addition to the type of improvements considered by SquareImp, LogImp searches for a certain type of local improvement of logarithmic size. In doing so, it obtains an approximation guarantee of $\frac{d-1+\epsilon _d}{2}$ for the MWIS in d-claw free graphs for $d\ge 3$, where $0\le \epsilon _d \le 1$ and $\lim _{d\rightarrow \infty } \epsilon _d = 0$. While we can only guarantee a quasi-polynomial running time for the MWIS, we manage to obtain a polynomial-time $\frac{k+\epsilon _{k+1}}{2}$-approximation for our main focus, the weighted k-Set Packing Problem, by means of color coding.

We further prove this result to be asymptotically tight by providing examples which show that any local improvement algorithm that, for an arbitrarily chosen, but fixed parameter $\alpha \in \mathbb {R}$, searches for local improvements of $w^\alpha$ of size $\mathcal {O}(\log (|\mathcal {S}|))$, cannot produce an approximation guarantee better than $\frac{k}{2}$ for the weighted k-Set Packing Problem with $k\ge 3$.

The latter significantly extends the state of knowledge in terms of lower bound examples. Even more importantly, we can finally (at least asymptotically) answer the long-standing question of how far one can get by using pure local search in the weighted setting. In doing so, we are also the first ones to port the idea of searching for local improvements of logarithmic size, which has proven very successful for unit weights [5, 6, 9, 10, 19], to the weighted setting.

The rest of this paper is organized as follows: Sect. 3 recaps some of the definitions and main results from [2] that we will employ in the analysis of our local improvement algorithm LogImp in Sect. 4. Section 5 then sketches our lower bound construction and Sect. 6 provides a brief conclusion.

3 Preliminaries

Definition 1

(Neighborhood [2]). Given an undirected graph $G=(V,E)$ and subsets $U,W\subseteq V$ of its vertices, we define the neighborhood N(U, W) of U in W as $N(U,W):=\{w\in W:\exists u\in U: \{u,w\}\in E \vee u=w\}.$ For $u\in V$ and $W\subseteq V$, we write N(u, W) instead of $N(\{u\}, W)$.

Notation

Given $w:V\rightarrow \mathbb {R}$ and $U\subseteq V$, we write $w^2(U):=\sum _{u\in U} w^2(u)$.

Definition 2

([2]). Given an undirected graph $G=(V,E)$, a weight function $w:V\rightarrow \mathbb {R}_{\ge 0}$ and an independent set $A\subseteq V$, we say that a vertex set $B\subseteq V$ improves $w^2(A)$ if B is independent in G and $w^2((A\setminus N(B,A))\cup B) > w^2(A)$ holds. For a claw C in G, we say that C improves $w^2(A)$ if $T_C$ does and call $T_C$ a claw-shaped improvement in this case. We further define a 0-claw to consist of a single talon and an empty center.

Note that in contrast to the introduction, we do not require a local improvement B to be disjoint from A anymore. Further observe that an independent set B improves A if and only if we have $w^2(B)>w^2(N(B,A))$.

Using the notation introduced above, Berman’s algorithm SquareImp [2] can now be formulated as in Algorithm 1. As all weights are positive, every $v\not \in A$ such that $A\cup \{v\}$ is independent constitutes the talon of a 0-claw improving $w^2(A)$, so the algorithm returns a maximal independent set.

The main idea of the analysis of SquareImp presented in [2] is to charge the vertices in A for preventing adjacent vertices in an optimum solution $A^*$ from being included into A. The latter is done by spreading the weight of the vertices in $A^*$ among their neighbors in the maximal independent set A in such a way that no vertex in A receives more than $\frac{d}{2}$ times its own weight. The suggested distribution of weights proceeds in two steps:

First, each vertex $u\in A^*$ invokes costs of $\frac{w(v)}{2}$ at each $v\in N(u,A)$. As G is d-claw free, no vertex $v\in A$ can have more than $d-1$ neighbors in $A^*$. This implies that the total amount of weight v receives in this step is bounded by $|N(v,A^*)|\cdot \frac{w(v)}{2}\le (d-1)\cdot \frac{w(v)}{2}$.

In a second step, each vertex $u\in A^*$ sends an amount of $w(u)-\frac{w(N(u,A))}{2}$ to a heaviest neighbor it possesses in A, which is captured by the following definition of charges:

Definition 3

(Charges [2]). For each $u\in A^*$, pick a vertex $v\in N(u,A)$ of maximum weight and call it n(u) (recall that A is maximal).

For $u\in A^*$ and $v\in A$, define

$$\mathrm {charge}(u,v):={\left\{ \begin{array}{ll} w(u)-\frac{w(N(u,A))}{2} &{},\text { if }v=n(u)\\ 0&{},\text { otherwise} \end{array}\right. }.$$

As we have already seen that each vertex $v\in A$ receives at most $\frac{d-1}{2}\cdot w(v)$ during the first step of the weight distribution, it suffices to show that the total amount of positive charges it has to pay is bounded by $\frac{w(v)}{2}$. In order to prove this, we want to exploit the fact that when SquareImp terminates, there is no improving claw centered at v. To this end, suppose that we want to construct an improving claw C centered at v and consider adding $u\in N(v,A^*)$ to its set $T_C$ of talons. On the one hand, this increases $w^2(T_C)$ by $w^2(u)$. On the other hand, $w^2(N(T_C,A))$ may also increase by up to $w^2(N(u,A)\setminus \{v\})$ (if our claw should be centered at v, we have to pay for v anyways). In case $w^2(u) > w^2(N(u,A)\setminus \{v\})$, we surely want to add u to our claw, otherwise, we may choose not to. This is captured by the definition of the contribution:

Definition 4

(Contribution [16]). Define a contribution map

$\mathrm {contr}:A^*\times A\rightarrow \mathbb {R}_{\ge 0}$ by setting

$$\mathrm {contr}(u,v):={\left\{ \begin{array}{ll}\max \left\{ 0,\frac{w^2(u)-w^2(N(u,A)\setminus \{v\})}{w(v)}\right\} &{}, \text { if } v\in N(u,A)\\ 0 &{},\text { else} \end{array}\right. }.$$

The fact that there is no improving claw directly implies that the total contribution to $v\in A$ is bounded by w(v). Moreover, a simple calculation shows that $2\cdot \mathrm {charge}(u,v)\le \mathrm {contr}(u,v)$ for all $u\in N(v,A^*)$ [16]. This finishes the analysis of SquareImp.

4 Our Algorithm LogImp

Our algorithm LogImp (Algorithm 2) starts with the empty solution, and then iteratively checks for the existence of improving claws as in Berman’s algorithm SquareImp and another type of local improvement, which we call circular. It corresponds to a cycle of logarithmically bounded size in a certain auxiliary graph. In particular, when LogImp terminates, there cannot be any further improving claw, so we can apply the analysis of SquareImp presented in Sect. 3 to our algorithm. Similar to [16], the key idea in analyzing LogImp is the following: Either the analysis of SquareImp is far enough from being tight to achieve the desired approximation ratio, or the instance at hand bears a certain structure that allows us to derive the existence of a circular improvement. But this contradicts the termination criterion of LogImp. Our main result is the following:

Theorem 5

There is a sequence $(\epsilon _d)_{d\ge 3}\in [0,1]^{\mathbb {N}_{\ge 3}}$ with $\lim _{d\rightarrow \infty }\epsilon _d =0$ such that LogImp yields a $\frac{d-1+\epsilon _d}{2}$-approximation for the MWIS in d-claw free graphs.

As applying the analysis of SquareImp to LogImp proves that the approximation guarantee of LogImp is no larger than $\frac{d}{2}$, it suffices to show that for every $\delta >0$, there is $d_0\ge 3$ such that for any $d\ge d_0$, LogImp is a $\frac{d-1+\delta }{2}$-approximation for the MWIS in d-claw free graphs.

Fix $\delta > 0$, denote the solution returned by LogImp by A, and let $A^*$ be an optimum solution. Moreover, fix two maps n and $n_2$ mapping each vertex in $V\setminus A$ to a heaviest neighbor in A, and each vertex in $V\setminus A$ with at least two neighbors in A to a second heaviest neighbor in A, respectively.

4.1 Classification of Vertices from $A^*$

We now provide a classification of the vertices in $A^*$ that helps us to understand the structural properties of near-tight instances. For this purpose, we fix two constants $0<\epsilon '\ll \sqrt{\epsilon '}\ll \tilde{\epsilon }<\delta <1$ subject to certain inequalities (see [17]).

Lemma 6

Each $u\in A^*$ with $\mathrm {charge}(u,n(u))>0$ is of one of the following three types:

single: $\frac{w(u)}{w(n(u))}\in [1-\sqrt{\epsilon '},1+\sqrt{\epsilon '}]$ and $w(N(u,A))\le (1+\sqrt{\epsilon '})\cdot w(n(u))$

double: $|N(u,A)|\ge 2$, $\frac{w(u)}{w(n(u))}\in [1-\sqrt{\epsilon '},1+\sqrt{\epsilon '}]$, $\frac{w(n_2(u))}{w(n(u))}\in [1-\sqrt{\epsilon '},1]$ and $(2-\sqrt{\epsilon '})\cdot w(n(u))\le w(N(u,A))<2\cdot w(u)$

contributive: $\mathrm {contr}(u,n(u))\ge 2\cdot \mathrm {charge}(u,n(u))+\frac{\epsilon '}{2}\cdot w(u)$

For a single vertex u, the heaviest neighbor n(u) of u in A has almost the same weight as u and makes up almost all of N(u, A) in terms of weight. Single vertices correspond to vertices of degree 1 to A in the unit weight case.

For a double vertex u, its two heaviest neighbors in A, n(u) and $n_2(u)$, have roughly the same weight as u and make up most of N(u, A). Double vertices can be thought of as having degree 2 to A.

For a contributive vertex u, we gain a constant fraction of w(u) in the analysis.

Lemma 7

Each $u\in A^*$ with $\mathrm {charge}(u,n(u))\le 0$ is of one of the following three types:

payback: $w(N(u,A))\ge (2+\epsilon ')\cdot w(u)$

good: $|N(u,A)|\ge 2$, $\frac{w(u)}{w(n(u))}\in \left[ 1-\sqrt{2\epsilon '},\frac{1}{1-\sqrt{2\epsilon '}}\right]$, $\frac{w(n_2(u))}{w(n(u))}\in [1-\sqrt{2\epsilon '},1]$ and $2\cdot w(u)\le w(N(u,A))< (2+\epsilon ')\cdot w(u)$

contributive: $\mathrm {contr}(u,n(u))\ge \frac{\epsilon '}{2}\cdot w(u)=\max \{0,2\cdot \mathrm {charge}(u,n(u))\}+\frac{\epsilon '}{2}\cdot w(u)$

The weight of a payback vertex u is overestimated in the first step of the weight distribution, so u can pay back $\frac{\epsilon '}{2}\cdot w(u)$, improving our bound on $w(A^*)$.

For a good vertex $u\in A^*$, n(u) and $n_2(u)$ have almost the same weight as u and make up most of N(u, A) in terms of weight. Like double vertices, good vertices can be thought of as having degree 2 to A.

4.2 Missing, Profitable and Helpful Vertices

We now discuss the role the different types of vertices in $A^*$ play in our analysis. We start by recalling that in the first step of the weight distribution in the analysis of SquareImp, each $v\in A$ pays $|N(v,A^*)|\cdot \frac{w(v)}{2}$, which we bound by $(d-1)\cdot \frac{w(v)}{2}$. In particular, if the number of neighbors of v in $A^*$ happens to be less than $d-1$ (we say that v has $d-1-|N(v,A^*)|$ missing neighbors in this case), we gain $\frac{w(v)}{2}$ for each missing neighbor of v (cf. Lemma 8).

We partition the neighbors a vertex $v\in A$ has in $A^*$ into those that are helpful for v, and those that are profitable for v. While helpful vertices are those vertices that would be considered neighbors of v in an unweighted approximation of our instance, and that help us to construct local improvements of logarithmic size, profitable vertices are the remaining neighbors that in some sense keep the instance from being close to unweighted and hence, tight. Therefore, they improve the analysis (i.e. our bound on $w(A^*)$ profits from these). Formally speaking, we say that $u\in N(v,A^*)$ is helpful for v if u is single and $v=n(u)$, or if u is double or good and $v\in \{n(u),n_2(u)\}$. Otherwise, we call u profitable for v.

One can show that for each profitable neighbor that a vertex $v\in A$ possesses in $A^*$, we gain a constant fraction of w(v) in bounding $w(A^*)$. Intuitively, this is because for every profitable neighbor u of v, v makes the estimate $2\cdot \mathrm {charge}(u,n(u))\le \mathrm {contr}(u,n(u))$ less tight. Lemma 8 formalizes the way missing and profitable neighbors improve our bound on $w(A^*)$.

Lemma 8

$$\begin{aligned} w(A^*)&\le \frac{d}{2}\cdot w(A)-\sum _{v\in A}(d-1-|N(v,A^*)|)\cdot \frac{w(v)}{2}\\&-\sum _{v\in A}\frac{\epsilon '}{10}\cdot w(v)\cdot \# \text { profitable neighbors of } v. \end{aligned}$$

This implies that if the total weight of vertices $v\in A$ with more than $\frac{d-1}{4}$ neighbors that are not helpful, and, hence, missing or profitable for v, is at least $\frac{20}{\epsilon '\cdot (d-1)}\cdot w(A)$, we obtain $w(A^*)\le \frac{d-1}{2}\cdot w(A)$ and are therefore done. As a consequence, we can assume that in terms of weight, all but a fraction of $\frac{20}{\epsilon '\cdot (d-1)}$ of the vertices in A have at least $\frac{3}{4}\cdot (d-1)$ helpful neighbors.

We can further bound the number of these neighbors that are single: If we choose $\epsilon '$ small enough, each single helpful neighbor u of v contributes a large constant fraction of w(u) and, hence, also w(v), to $v=n(u)$. For d large enough, no $v\in A$ can therefore have more than $\frac{d-1}{4}$ neighbors that are single and helpful for v, as this would result in an improving claw. This allows us to conclude that the total weight of all vertices from A with at least $\frac{d-1}{2}$ neighbors in $A^*$ that are helpful for them and either good or double (i.e. correspond to vertices of degree 2 to A in the unweighted setting) is at least $\left( 1-\frac{20}{\epsilon '\cdot (d-1)}\right) \cdot w(A)$.

4.3 Local Improvements of Logarithmic Size

Our goal is to use these neighbors towards a local improvement of logarithmic size. In order to get a better idea of what we are aiming at, we take a brief detour and recapitulate how these vertices are handled in the unit weight case. In [9], an auxiliary graph $G_A$ is constructed, the vertices of which correspond to the vertices in the current solution A. Each vertex from an optimum solution $A^*$ with exactly one neighbor in A creates a loop on that neighbor, while every $u\in A^*$ with exactly two neighbors in A results in an edge connecting these. Now, it is not hard to see that there is a one-to-one correspondence between local improvements only featuring vertices from $A^*$ with degree one or two to A, and sub-graphs of $G_A$ with more edges than vertices. A minimal such sub-graph is called a binocular [3]. Now, a result by Berman and Fürer [3] comes into play:

Lemma 9

([3]). For any $s\in \mathbb {N}_{>0}$, any graph $G=(V,E)$ with $|E|\ge \frac{s+1}{s}\cdot |V|$ contains a binocular of size at most $4\cdot s\cdot \log (|V|)$.

In particular, Lemma 9 implies the existence of a cycle of the given size. Moreover, if the number of vertices of degree 1 or 2 to A exceeds $(1+\epsilon )\cdot |A|$, one can find local improvements of size $\mathcal {O}(\frac{1}{\epsilon }\cdot \log (|A|))$, which is one of the key ingredients of the result in [9].

We would like to port this approach to our weighted setting where vertex weights are locally similar. If we could ensure that for each good or double vertex u, its squared weight is at least as large as the average squared weight of its neighbors n(u) and $n_2(u)$, plus the squared weight of neighbors of u in A other than n(u) and $n_2(u)$, then we would be done since in a binocular, every vertex has degree at least two, and there is at least one vertex of degree more than two. However, this need not be the case in general, and even if we only lose an $\epsilon '$ fraction of the weight of each vertex involved, the total loss might be arbitrarily large if we consider improvements of logarithmic size. In order to overcome this issue, we have to make sure that locally, we have some additional vertices with a positive contribution to the endpoints of the edges that we can add to guarantee that we can make up for the slight inaccuracies caused by the weight differences.

To this end, for $v\in A$, we consider the set of vertices $T_v$ sending positive charges to v (in particular, $v=n(u)$ for all $u\in T_v$), and define $\bar{B}$ to consist of all $v\in A$ for which the total contribution of $T_v$ to v exceeds $\tilde{\epsilon }\cdot w(v)$. (Recall that $0<\epsilon '\ll \sqrt{\epsilon '}\ll \tilde{\epsilon }<\delta <1$.) Then all vertices $v\in A\setminus \bar{B}$ receive charges of at most $\frac{\tilde{\epsilon }}{2}\cdot w(v)$. Hence, if $w(\bar{B})\le \frac{40}{\epsilon '\cdot (d-1)}\cdot w(A)$, we can bound the total weight the vertices in A receive in the second step of the weight distribution by

$$\begin{aligned} \frac{\tilde{\epsilon }}{2}\cdot w(A\setminus \bar{B})+\frac{1}{2}\cdot w(\bar{B})\le \left( \tilde{\epsilon }+\frac{40}{\epsilon '\cdot (d-1)}\right) \cdot \frac{w(A)}{2}. \end{aligned}$$

For d large enough, this is at most $\delta \cdot \frac{w(A)}{2}$, yielding the desired statement. This means that we can assume $w(\bar{B})> \frac{40}{\epsilon '\cdot (d-1)}\cdot w(A)$ in the following. In particular, this means that the set B consisting of all vertices in $\bar{B}$ that have at least $\frac{d-1}{2}$ helpful neighbors that are good or double is of weight at least $w(B)\ge w(\bar{B})-\frac{20}{\epsilon '\cdot (d-1)}\cdot w(A)> \frac{20}{\epsilon '\cdot (d-1)}\cdot w(A)$.

Our goal for the rest of the analysis is to lead this assumption to a contradiction, implying that we have to be in one of the previously handled cases where we obtain the desired approximation guarantee of $\frac{d-1+\delta }{2}$. To this end, we want to show that the current setting implies the existence of a circular improvement. We call a local improvement $X\subseteq V\setminus A$ circular if

• $\exists U\subseteq X$ s.t. $|U|\le 4\cdot \log (|V|)$, each $u\in U$ has at least two neighbors in A and $C:=(\bigcup _{u\in U}\{n(u), n_2(u)\}, \{e_u=\{n(u), n_2(u)\}, u\in U\})$ is a cycle.

• If we let $Y_v:=\{x\in X\setminus U: n(x)=v\}$, then $X=U\cup \bigcup _{v\in V(C)} Y_v$.

• $w^2(u)+\frac{1}{2}\cdot \left( \sum \limits _{z\in Y_{n(u)}}\mathrm {contr}(z,n(u))\cdot w(n(u))+\sum \limits _{z\in Y_{n_2(u)}}\mathrm {contr}(z,n_2(u))\cdot w(n_2(u))\right)$ $> \frac{1}{2}\cdot (w^2(n(u))+w^2(n_2(u)))+w^2(N(u,A)\setminus \{n(u),n_2(u)\})$ for all $u\in U$.

The intuition behind this definition is the following: Similar to the unweighted case, we build up an auxiliary graph H on the vertex set A, where each vertex $u\in V\setminus A$ with at least two neighbors in A induces an edge between its two heaviest ones n(u) and $n_2(u)$. For the analysis, we will only consider edges induced by double or good vertices from $A^*$, i.e. those corresponding to vertices of degree two in the unweighted setting. The backbone of our circular improvement is given by a cycle C of logarithmic size in H. Additionally, for each $v\in V(C)$, we can add some additional vertices u with $n(u)=v$ that contribute a positive amount to v. Now, we want to cover for the weight of each $v\in V(C)\subseteq N(X,A)$ by using the vertices corresponding to the two incident edges in C as well as the contributions from the vertices in $Y_v$. This means that for each edge induced by $u\in U$, we would like $w^2(u)$, together with half of the contributions to n(u) and $n_2(u)$, to be able to pay for all neighbors of u in A other than n(u) and $n_2(u)$, as well as half of n(u) and $n_2(u)$, which is precisely the last constraint.

Now, in order to find such circular improvements when $w(B)> \frac{20}{\epsilon '\cdot (d-1)}\cdot w(A)$, we consider the auxiliary graph $H'$ with vertex set A, where each double or good vertex u induces an edge between n(u) and $n_2(u)$, provided at least one of them is contained in B. For $v\in B$, the total contribution of $T_v$ to v is at least $\tilde{\epsilon }\cdot w(v)$, whereas each good or double vertex contributes at most $\mathcal {O}(\sqrt{\epsilon '})\cdot w(v)$ with $\sqrt{\epsilon '}\ll \tilde{\epsilon }$. Hence, each cycle C in $H'$ of logarithmic size gives rise to a circular improvement by choosing $Y_v$ to contain all of $T_v$ except for the at most two vertices inducing edges incident to v if $v\in V(C)\cap B$, and setting $Y_v:=\emptyset$ otherwise.

To finally see that $H'$ contains a cycle of logarithmic size, we use the facts that the weighted average degree $\frac{1}{w(A)}\cdot \sum _{v\in A} w(v)\cdot |\delta _{H'}(v)|$ is at least $\frac{d-1}{2}\cdot \frac{w(B)}{w(A)}> \frac{10}{\epsilon '}$, together with the fact that the weights of the endpoints of each edge only differ by a factor close to 1, to conclude that there has to be a sub-graph of $H'$ that is dense enough to apply Lemma 9. (Note that if we had unit weights, this would follow immediately since the average degree would be at least $\frac{10}{\epsilon '}>2$.) This implies the existence of a circular improvement, contradicting the termination criterion of LogImp and finishing the proof. See [17] for a more detailed analysis.

4.4 A Polynomial Running Time

To achieve a polynomial number of iterations of LogImp, we scale and truncate the weight function as in [4] and [2]. This only results in an arbitrarily small additive error in the approximation guarantee.

In order to search for circular improvements in polynomial time, we employ the color coding technique in a similar fashion as in [9]. Note that this is the only point where we need the additional structural properties of a k-Set Packing instance (as opposed to an instance of the MWIS in $k+1$-claw free graphs). Detailed descriptions and proofs can be found in [17].

5 The Lower Bound

In this section, we show that our result is asymptotically best possible in the sense of Theorem 10.

Theorem 10

Let $k\ge 3$, $\alpha \in \mathbb {R}$, $0<\epsilon <1$ and $C>0$. Then for each $N_0\in \mathbb {N}$, there exist an instance $(\mathcal {S}, w)$ of the weighted k-Set Packing Problem with $|\mathcal {S}|\ge N_0$ and feasible solutions $A,A^*\subseteq \mathcal {S}$, such that for A, there is no local improvement of size at most $C\cdot \log (|\mathcal {S}|)$ with respect to $w^\alpha$, but $w(A^*)\ge \frac{k-\epsilon }{2}\cdot w(A)$.

Proof

For $k\le 2$, there is nothing to show and for $\alpha \le 0$, we can just choose the weights in A to be arbitrarily small. Hence, we can assume $k\ge 3$ and $\alpha >0$. Now, there is a result by Erdős and Sachs [8] telling us that for every $N_0\in \mathbb {N}$, there is a k-regular graph H on $|V(H)|\ge N_0$ vertices such that the girth of H, i.e. the minimum length of a cycle in H, is at least $\frac{\log (|V(H)|)}{\log (k-1)}-1$. Consider the graph G with vertex set $V(G):=V(H)\cup E(H)$ and edge set $E(G):=\{\{v,e\}:v\in e\in E(H)\}$, i.e. each edge of H is connected via edges in G to both of its endpoints. We define $\mathcal {S}:=\{\delta _G(x), x\in V(G)\}$, where $\delta _G(x)$ is the set of incident edges of x in G. By k-regularity of H, $|\delta _G(v)|=k\ge 3$ for $v\in V(H)$ and $|\delta _G(e)|=2$ for $e\in E(H)$, so each element of $\mathcal {S}$ has cardinality at most k. By definition, G is simple, so no two vertices share more than one edge. As all degrees are at least two, the sets $\delta _G(x),x\in V(G)$ are pairwise distinct. Finally, V(H) and E(H) constitute independent sets in G, implying that $A:=\{\delta _G(v), v\in V(H)\}$ and $A^*:=\{\delta _G(e),e\in E(H)\}$ each consist of pairwise disjoint sets. We define positive weights on $\mathcal {S}$ by setting $w(\delta _G(v)):=1$ for $v\in V(H)$ and $w(\delta _G(e)):=(1-\bar{\epsilon })^{\frac{1}{\alpha }}$, where $\bar{\epsilon }>0$ is chosen such that $\frac{1}{\bar{\epsilon }}\in \mathbb {N}$ and $(1-\bar{\epsilon })^{\frac{1}{\alpha }}\ge 1-\frac{\epsilon }{k}$. By k-regularity of H, $|A^*|=|E(H)|=\frac{k}{2}\cdot |V(H)|=\frac{k}{2}\cdot |A|$, so $w(A^*)\ge \frac{k-\epsilon }{2}\cdot w(A)$. To see that there is no local improvement X of $w^\alpha (A)$ with $|X|\le C\cdot \log (|V(G)|)=C\cdot \log (\frac{k+2}{2}\cdot |V(H)|)$, first note that we can w.l.o.g. assume $X\subseteq \mathcal {S}\setminus A=A^*$ (otherwise, consider $X\setminus A$). Then, X being a local improvement implies that $|X|>\frac{1}{1-\bar{\epsilon }}\cdot |\{y\in A:\exists x\in X: y\cap x\ne \emptyset \}|$ by our choice of weights. But the sets from A that X intersects are precisely the sets $\delta _G(v)$ for those vertices $v\in V(H)$ that are endpoints of edges $e\in E(H)$ with $\delta _G(e)\in X$. Hence, we have found as sub-graph J of H with

$$\begin{aligned} C\cdot \log \left( \frac{k+2}{2}\cdot |V(H)|\right) \ge |X|=|E(J)|> \frac{1}{1-\bar{\epsilon }}\cdot |V(J)|\ge (1+\bar{\epsilon })\cdot |V(J)|, \end{aligned}$$

which implies the existence of a cycle of length $\frac{4}{\bar{\epsilon }}\cdot \log (C\cdot \log (\frac{k+2}{2}\cdot |V(H)|))$ by Lemma 9. But as a function of |V(H)|, this grows asymptotically slower than our lower bound of $\frac{\log (|V(H)|)}{\log (k-1)}-1$ on the girth, resulting in a contradiction for $N_0$ and, hence, |V(H)| chosen large enough. For a more detailed proof, see [17].

6 Conclusion

In this paper, we have seen how to use local search to approximate the weighted k-Set Packing Problem with an approximation ratio that gets arbitrarily close to $\frac{k}{2}$ as k approaches infinity. At the cost of a quasi-polynomial running time, this result applies to the more general setting of the Maximum Weight Independent Set Problem in d-claw free graphs, yielding approximation ratios arbitrarily close to $\frac{d-1}{2}$. Moreover, we have seen that this result is asymptotically best possible in the sense that for no $\alpha \in \mathbb {R}$, a local improvement algorithm for the weighted k-Set Packing Problem that considers local improvements of $w^\alpha$ of logarithmically bounded size can produce an approximation guarantee better than $\frac{k}{2}$.

As a consequence, our paper seems to conclude the story of (pure) local improvement algorithms for both the MWIS in d-claw free graphs and the weighted k-Set Packing Problem. Hence, the search for new techniques beating the threshold of $\frac{d-1}{2}$, respectively $\frac{k}{2}$, is one of the next goals for research in this area.