This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware.
Informal statement
Recall the NP-complete problems Exact Cover by 3-Sets and 3-Dimensional Matching, and consider their natural generalizations Exact Cover by Equally-Sized Sets and Multi-Dimensional Matching, where the number “3” is no longer fixed and given as part of input. Clearly, these four problems are reducible to one another because they are NP-complete.
Informally, the question is the following: is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching so that “far from yes” instances of the former are mapped to “far from yes” instances of the latter, where “far from yes” means that “the size of the minimum cover is large”?
(There are other sensible formulations of “far from yes,” such as “the size of the maximum packing is small,” but in this question we are particularly interested in the formulation stated above.)
Formal statement
Consider the following two optimization problems.
Minimum Cover by Equally-Sized Sets
Instance: k∈ℕ, a finite set X and a collection F of subsets of X such that each set E∈F consists of exactly k elements.
Solution: A cover C of X in F.
Objective: Minimize k|C|/|X|. (This is clearly equivalent to minimizing |C|, but the way it is stated is relevant because we will later use the optimal value.)
(This is a generalization of Exact Cover by Equally-Sized Sets.)
Minimum Multi-Dimensional Cover
Instance: k, X and F as defined in Minimum Cover by Equally-Sized Sets, and a partition of X into k sets X1, …, Xk each of size |X|/k such that every set E∈F contains exactly one element in Xi for each 1≤i≤k.
Solution, Objective: Same as Exact Cover by Equally-Sized Sets.
(This is a generalization of Multi-Dimensional Matching.)
Minimum Multi-Dimensional Cover can be viewed as a special case of Minimum Cover by Equally-Sized Sets.
We would like to compare the approximability of these two problems at the location 1 (in the sense of “gap location” [Pet94]). More precisely,
Question. Does there exist a polynomial-time computable function f which maps every instance I of Minimum Cover by Equally-Sized Sets to an instance f(I) of Minimum Multi-Dimensional Cover so that the following conditions are both satisfied?
- If the optimal value of I is equal to 1, the optimal value of f(I) is also equal to 1.
- There exists a constant c>0 such that for every instance I of Minimum Cover by Equally-Sized Sets, the optimal value of f(I) is at least c times the optimal value of I.
It is more desirable if the function f increases the size of the set X only linearly, but I do not make this a requirement for this question.
Known facts
On the good news side, we can apply the greedy algorithm for Set Cover to both problems to obtain a (ln k + O(1))-approximate solution [Joh74] and a (ln |X| − ln ln |X| + O(1))-approximate solution [Sla97].
On the bad news side, I do not know how much of the inapproximability results of Set Cover can be applied to obtain a result about hardness of these special cases, let alone hardness of these problems at the location 1. The only result that I am aware of about the hardness of Minimum Multi-Dimensional Cover at the location 1 is the following result by Petrank [Pet94]: there exists a constant c>0 such that it is NP-complete to decide, given an instance of Minimum Multi-Dimensional Cover, whether the optimal value is equal to 1 or greater than c, even if k is fixed to k=3.
References
[Joh74] David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256–278, Dec. 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9
[Pet94] Erez Petrank. The hardness of approximation: Gap location. Computational Complexity, 4(2):133–157, April 1994. http://dx.doi.org/10.1007/BF01202286
[Sla97] Petr Slavík. A tight analysis of the greedy algorithm for set cover. Journal of Algorithms, 25(2):237–254, Nov. 1997. http://dx.doi.org/10.1006/jagm.1997.0887
