The minimum feasible tileset problem (Q666670): Difference between revisions

This paper initiates the study of the Minimum Feasible Tileset problem (MFT), which is rather natural. For clarity, MFT should not be confused with the ``geometric notion of tiling problems'', such as those for Wang tiles (i.e., the idea there would be, for example, whether a set of tiles with certain geometric rules for placement can be used to tile the plane). Rather, MFT is more akin to a covering problem, where one wishes to ``cover'' certain desired sequences of symbols/patterns. Rather than defining the problem formally in this review, we give an analogy: Suppose one has a team of \(n\) soccer players, and a set \(F\) of possible soccer skills (e.g., shooting, stealing, etc.). But each player naturally can only master a small set of skills in a lifetime, say 2 skills. The question is, roughly, whether there is a way to pick for each player \(p_i\), some set of 2 skills from \(F\), so that for any opposing team one faces (i.e., one may formalize this by listing configurations of weaknesses of the opposing team), our team has the skills necessary to overcome the weaknesses of the opposition. More accurately, the paper studies the optimization version of this problem, in which one tries to minimize the size of the soccer team required to be able to cover all of the opposing team's weaknesses. The paper does an arguably thorough job initiating this study. First, it shows the problem is NP-hard, and in fact APX-hard, meaning it is unlikely one can approximately solve MFT within any desired fixed relative error \(r\) in polynomial time. The authors then show, however, that while a PTAS is unlikely, a constant factor approximation ratio is possible -- indeed, the paper gives a 4/3-approximation algorithm for MFT. This algorithm is strongly motivated by structural insights into optimal MFT tiling solutions developed in the paper which show that when properly embedded as a graph-theoretical problem, optimal MFT solutions look like forests without loss of generality. The paper finally gives algorithms along the direction of fixed-parameter tractibility; for example, the authors show that if in MFT the number of ``weakness configurations'' of the oppositing soccer team is constant, then MFT can be solved in poly-time. This roughly follows by encoding MFT as an integer linear program (ILP), and using known results that ILP is fixed-parameter tractable relative to the number of variables.