1
$\begingroup$

My application problem can be modeled as maximum k-parity k-set packing problem, which is NP-hard. I know that maximum matching is polynomial time, hence I want to reduce k-parity k-set packing into bipartite maximum matching. I am wondering if there is any relation between their size.

Maximum k-parity k-set packing problem: We're given a universe $U$, which is a union of $k$ disjoint sets, $ U = V_1 \cup \cdots \cup V_k$, and a family $ \mathcal{S} $ of subsets of $ U$, each $S$ contains exactly one vertex from each set, i.e., $S \in V_1 \times \cdots \times V_k$. A packing is a subfamily ${\mathcal {C}} \subseteq {\mathcal {S}} $ of sets such that all sets in ${\mathcal{C}}$ are pairwise disjoint. The size of that packing is $|{\mathcal {C}}|$. We are looking for the maximum-size packing.

In order to take advantage of polynomial time maximum matching we reduce $U$ to $U' = V_i \times V_j, i , j = 1, \cdots, k$ and $\mathcal{S}'$ be a family of subsets of $U$ such that each $S'$ contains exactly one vertex from $V_i$ and $V_j$. Let $d_{i,j}$ be the size of maximum matching and $d = \min_{i,j} \{d_{i,j} \}$.

For example in the figure below: $|C| = 2, d_{2,3} = d_{1,2} = d_{1,3} = 2$ hence $d = \min(2,2,2) = 2$.

My question: is this inequality true $|{\mathcal {C}}| \le d \le k \times |{\mathcal {C}}|$ ?

I think $|{\mathcal {C}}| \le d$ is obvious, do we also have $ d \le k \times |{\mathcal {C}}|$?

$\endgroup$
1
$\begingroup$

Consider the case $k=3$, and the following set system: $$ (a_1,b_1,c),\ldots,(a_n,b_n,c) \\ (a'_1,b',c'_1),\ldots,(a'_n,b',c'_n) \\ (a'',b''_1,c''_1),\ldots,(a'',b''_n,c''_n) $$ Every packing contains at most 3 sets, but $d=n+2$.

$\endgroup$
  • $\begingroup$ After doing some more research, I guess if I want k-approximation algorithm I should go with LP relaxation. :) $\endgroup$ – Pepper M Mar 19 '17 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.