×

The minimum feasible tileset problem. (English) Zbl 1436.68398

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.

MSC:

68W25 Approximation algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q27 Parameterized complexity, tractability and kernelization
90C10 Integer programming
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bansal, N., Caprara, A., Sviridenko, M.: A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput. 39(4), 1256-1278 (2009) · Zbl 1201.90071 · doi:10.1137/080736831
[2] Bezzo, N.; Cortez, RA; Fierro, R., Exploiting heterogeneity in robotic networks, No. 57, 53-75 (2013), Berlin, Heidelberg · doi:10.1007/978-3-642-33971-4_4
[3] Biedl, T., Chan, T., Ganjali, Y., Hajiaghayi, M., Wood, D.: Balanced vertex-orderings of graphs. Discrete Appl. Math. 148(1), 27-48 (2005) · Zbl 1060.05088 · doi:10.1016/j.dam.2004.12.001
[4] Buchin, K., van Kreveld, M.J., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. J. Graph Algorithms Appl. 15(4), 533-549 (2011) · Zbl 1276.05081 · doi:10.7155/jgaa.00237
[5] Chen, J., Komusiewicz, C., Niedermeier, R., Sorge, M., Suchý, O., Weller, M.: Polynomial-time data reduction for the subset interconnection design problem. SIAM J. Discrete Math. 29(1), 1-25 (2015) · Zbl 1326.05147 · doi:10.1137/140955057
[6] Crescenzi, P.: A short guide to approximation preserving reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity (CCC)
[7] Cygan., M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 509-518 (2013)
[8] Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 68-81 (2012) · Zbl 1421.68072
[9] Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1-23:27 (2014) · Zbl 1321.68274 · doi:10.1145/2629620
[10] Disser, Y., Kratsch, S., Sorge, M.: The minimum feasible tileset problem. In: Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA ’14), LNCS, vol. 8952, pp. 144-155. Springer, Heidelberg (2014) · Zbl 1417.68285
[11] Disser, Y., Matuschke, J.: Degree-constrained orientations of embedded graphs. J. Comb. Optim. 31(2), 758-773 (2016) · Zbl 1333.05202 · doi:10.1007/s10878-014-9786-1
[12] Du, D.-Z., Miller, Z.: Matroids and subset interconnection design. SIAM J. Discrete Math. 1(4), 416-424 (1988) · Zbl 0669.05021 · doi:10.1137/0401042
[13] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006) · Zbl 1143.68016
[14] Frank, A., Gyárfás, A.: How to orient the edges of a graph. Coll. Math. Soc. Janos Bolyai 18, 353-364 (1976)
[15] Frank, A., Tardos, É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49-65 (1987) · Zbl 0641.90067 · doi:10.1007/BF02579200
[16] Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H Freeman and Company, San Francisco (1979) · Zbl 0411.68039
[17] Gottlob, G., Greco, G.: Decomposing combinatorial auctions and set packing problems. J. ACM 60(4), 24 (2013) · Zbl 1281.91088 · doi:10.1145/2508028.2505987
[18] Hakimi, S.: On the degrees of the vertices of a directed graph. J. Frankl. Inst. 279(4), 290-308 (1965) · Zbl 0173.26404 · doi:10.1016/0016-0032(65)90340-6
[19] Johnson, D.S., Pollak, H.O.: Hypergraph planarity and the complexity of drawing Venn diagrams. J. Graph Theory 11(3), 309-325 (1987) · Zbl 0654.05055 · doi:10.1002/jgt.3190110306
[20] Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37(1), 27-35 (1991) · Zbl 0711.68045 · doi:10.1016/0020-0190(91)90246-E
[21] Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415-440 (1987) · Zbl 0639.90069 · doi:10.1287/moor.12.3.415
[22] Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Proceedings of the 35th International Colloquium on Automata (ICALP), pp. 575-586 (2008) · Zbl 1153.68562
[23] Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538-548 (1983) · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[24] Lundh, R., Karlsson, L., Saffiotti, A.: Autonomous functional configuration of a network robot system. Robot. Auton. Syst. 56(10), 819-830 (2008) · doi:10.1016/j.robot.2008.06.006
[25] Marek, C., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015) · Zbl 1334.90001
[26] Mittal, S.: A survey of techniques for architecting and managing asymmetric multicore processors. ACM Comput. Surv. 48(3), 1-38 (2016) · doi:10.1145/2856125
[27] Reinhard, D.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 5th edn. Springer, Berlin (2016)
[28] Rodney, G., Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013) · Zbl 1358.68006
[29] Schuurman, P., Woeginger, G.J.: Approximation schemes—a tutorial. http://www.win.tue.nl/ gwoegi/papers/ptas.pdf · Zbl 0943.68009
[30] Sviridenko, M., Ward, J.: Large neighborhood local search for the maximum set packing problem. In: 40th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 792-803 (2013) · Zbl 1336.68241
[31] van Bevern, R., Kanj, I., Komusiewicz, C., Niedermeier, R., Sorge,M.: Twins in subdivision drawings of hypergraphs. In: Proceedings of the 24th International Symposium on Graph Drawing & Network Visualization, LNCS, vol. 9801, pp. 67-80. Springer, Heidelberg (2016) · Zbl 1483.68262
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.