×

zbMATH — the first resource for mathematics

Combinatorial \(n\)-fold integer programming and applications. (English) Zbl 1451.90100
Summary: Many fundamental \(\mathsf{NP}\)-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for \(\mathsf{NP} \)-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of R. Hemmecke et al. [Math. Program. 137, No. 1–2 (A), 325–341 (2013; Zbl 1262.90104)], we develop a single-exponential algorithm for so-called combinatorial \(n\)-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to many relevant problems problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra’s algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial \(n\)-fold IPs, existence of an augmenting step implies existence of a “local” augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
MSC:
90C10 Integer programming
90C27 Combinatorial optimization
90C39 Dynamic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amir, A., Ficler, J., Roditty, L., Shalom, O.S.: On the efficiency of the Hamming C-centerstring problems. In: Proceedings of CPM 2014, Lecture Notes in Computer Science, vol. 8486, pp. 1-10 (2014) · Zbl 1407.68569
[2] Amir, A.; Landau, GM; Na, JC; Park, H.; Park, K.; Sim, JS, Efficient algorithms for consensus string problems minimizing both distance sum and radius, Theor. Comput. Sci., 412, 39, 5239-5246 (2011) · Zbl 1222.68417
[3] Avila, L.F., Garcıa, A., Serna, M.J., Thilikos, D.M.: A list of parameterized problems in bioinformatics. Tech. Rep. LSI-06-24-R, Technical University of Catalonia (2006)
[4] Boucher, C.; Ma, B., Closest string with outliers, BMC Bioinform., 12, S55 (2011)
[5] Boucher, C., Wilkie, K.: Why large closest string instances are easy to solve in practice. In: Proceedings of SPIRE 2010, Lecture Notes in Computer Science, vol. 6393, pp. 106-117 (2010)
[6] Bredereck, R.; Chen, J.; Faliszewski, P.; Guo, J.; Niedermeier, R.; Woeginger, GJ, Parameterized algorithmics for computational social choice: nine research challenges, Tsinghua Sci. Tech., 19, 4, 358-373 (2014)
[7] Bredereck, R.; Chen, J.; Hartung, S.; Kratsch, S.; Niedermeier, R.; Suchý, O.; Woeginger, GJ, A multivariate complexity analysis of lobbying in multiple referenda, J. Artif. Intell. Res., 50, 409-446 (2014) · Zbl 1342.91011
[8] Bredereck, R., Faliszewski, P., Niedermeier, R., Skowron, P., Talmon, N.: Elections with few candidates: Prices, weights, and covering problems. In: Proceedings of ADT 2015, Lecture Notes in Computer Science, vol. 9346, pp. 414-431 (2015) · Zbl 1403.68075
[9] Bulteau, L., Hüffner, F., Komusiewicz, C., Niedermeier, R.: Multivariate algorithmics for NP-hard string problems. Bull. EATCS 114, (2014) · Zbl 1409.68350
[10] Chrobak, M., Dürr, C., Hurand, M., Robert, J.: Algorithms for temperature-aware task scheduling in microprocessor systems. In: Proceedings of AAIM 2008, Lecture Notes in Computer Science, vol. 5034, pp. 120-130 (2008) · Zbl 1143.68341
[11] Chubanov, S., A polynomial-time descent method for separable convex optimization problems with linear constraints, SIAM J. Opt., 26, 1, 856-889 (2016) · Zbl 1338.90299
[12] Cormen, TH; Leiserson, CE; Rivest, RL, Introduction to Algorithms (1990), Cambridge: MIT Press, Cambridge
[13] Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)
[14] Dadush, D.; Peikert, C.; Vempala, S., Enumerative lattice algorithms in any norm via M-ellipsoid coverings, Proc. FOCS, 2011, 580-589 (2011) · Zbl 1292.68091
[15] De Loera, J.A., Hemmecke, R., Köppe, M.: Algebraic and geometric ideas in the theory of discrete optimization. MOS-SIAM series on optimization. SIAM, 14 (2013) · Zbl 1401.90012
[16] Dorn, B.; Schlotter, I., Multivariate complexity analysis of swap bribery, Algorithmica, 64, 1, 126-151 (2012) · Zbl 1283.68161
[17] Eisenbrand, F., Hunkenschröder, C., Klein, K.M.: Faster algorithms for integer programs with block structure. In: Proceedings of ICALP 2018, Leibniz International Proceedings in Informatics, vol. 107, pp. 49:1-49:13 (2018)
[18] Eisenbrand, F.; Shmonin, G., Carathéodory bounds for integer cones, Oper. Res. Lett., 34, 5, 564-568 (2006) · Zbl 1152.90662
[19] Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. In: Proceedings of SODA 2018, pp. 808-816 (2018) · Zbl 1410.90128
[20] Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Proceedings of SAGT 2009, Lecture Notes in Computer Science, vol. 5814, pp. 299-310 (2009)
[21] Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: The complexity of bribery in elections. In: Proceedings of AAAI 2006, pp. 641-646 (2006) · Zbl 1180.91090
[22] Fellows, MR; Gaspers, S.; Rosamond, FA, Parameterizing by the number of numbers, Theory Comput. Syst., 50, 4, 675-693 (2012) · Zbl 1253.68173
[23] Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proceedings of ISAAC 2008, Lecture Notes in Computer Science, vol. 5369, pp. 294-305. Springer, Berlin (2008) · Zbl 1183.68424
[24] Fiala, J.; Gavenčiak, T.; Knop, D.; Koutecký, M.; Kratochvíl, J., Parameterized complexity of distance labeling and uniform channel assignment problems, Discrete Appl. Math., 248, 46-55 (2018) · Zbl 1395.05143
[25] Fiala, J.; Golovach, PA; Kratochvíl, J., Parameterized complexity of coloring problems: treewidth versus vertex cover, Theor. Comput. Sci., 412, 23, 2513-2523 (2011) · Zbl 1216.68127
[26] Fishburn, PC, Condorcet social choice functions, SIAM J. Appl. Math., 33, 3, 469-489 (1977) · Zbl 0369.90002
[27] Frances, M.; Litman, A., On covering problems of codes, Theory Comput. Syst., 30, 2, 113-119 (1997) · Zbl 0868.94056
[28] Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Proceedings of IPEC 2013, Lecture Notes in Computer Science, vol. 8246, pp. 163-176 (2013) · Zbl 1406.68080
[29] Ganian, R.: Using neighborhood diversity to solve hard problems. Tech. rep. (2012). https://arxiv.org/abs/1201.3091
[30] Ganian, R.; Ordyniak, S., The complexity landscape of decompositional parameters for ILP, Artif. Intell., 257, 61-71 (2018) · Zbl 1451.90099
[31] Ganian, R.; Ordyniak, S.; Ramanujan, MS, Going beyond primal treewidth for (M)ILP, Proc. AAAI, 2017, 815-821 (2017)
[32] Goemans, MX; Rothvoß, T., Polynomiality for bin packing with a constant number of item types, Proc. SODA, 2014, 830-839 (2014) · Zbl 1421.68080
[33] Gramm, J.; Niedermeier, R.; Rossmanith, P., Fixed-parameter algorithms for closest string and related problems, Algorithmica, 37, 1, 25-42 (2003) · Zbl 1058.68119
[34] Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2, 2nd edn. Springer-Verlag, Berlin (1993) · Zbl 0837.05001
[35] Hemmecke, R.; Köppe, M.; Weismantel, R., Graver basis and proximity techniques for block-structured separable convex integer minimization problems, Math. Program., 145, 1-2, 1-18 (2014) · Zbl 1298.90057
[36] Hemmecke, R.; Onn, S.; Romanchuk, L., \(n\)-fold integer programming in cubic time, Math. Program., 137, 1-2, 325-341 (2013) · Zbl 1262.90104
[37] Hermelin, D.; Rozenberg, L., Parameterized complexity analysis for the closest string with wildcards problem, Theor. Comput. Sci., 600, 11-18 (2015) · Zbl 1329.68143
[38] Hochbaum, DS; Shanthikumar, JG, Convex separable optimization is not much harder than linear optimization, J. ACM, 37, 4, 843-862 (1990) · Zbl 0721.90060
[39] Jansen, B.M.P., Kratsch, S.: A structural approach to kernels for ILPs: treewidth and total unimodularity. In: Proceedings of ESA 2015, Lecture Notes in Computer Science, vol. 9294, pp. 779-791 (2015) · Zbl 06511817
[40] Jansen, K., Klein, K.: About the structure of the integer cone and its application to bin packing. In: Proceedings of SODA 2017, pp. 1571-1581 (2017) · Zbl 1410.90178
[41] Jansen, K., Rohwedder, L.: On integer programming and convolution. In: Proceedings of ITCS 2019, The Leibniz International Proceedings in Informatics, vol. 124, pp. 43:1-43:17 (2018)
[42] Kannan, R., Minkowski’s convex body theorem and integer programming, Math. Oper. Res., 12, 3, 415-440 (1987) · Zbl 0639.90069
[43] Knop, D.; Koutecký, M., Scheduling meets \(n\)-fold integer programming, J. Sched., 21, 5, 493-503 (2018) · Zbl 1418.90113
[44] Knop, D., Koutecký, M., Masařík, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: Treewidth and neighborhood diversity. In: Proceedings of WG 2017, Lecture Notes in Computer Sciencce, vol. 10520, pp. 344-357 (2017) · Zbl 06822010
[45] Knop, D., Koutecký, M., Mnich, M.: Combinatorial \(n\)-fold integer programming and applications. In: Proceedings of ESA 2017, The Leibniz International Proceedings in Informatics, vol. 87, pp. 54:1-54:14 (2017) · Zbl 1442.90129
[46] Knop, D., Koutecký, M., Mnich, M.: Voting and bribing in single-exponential time. In: Proceedings of STACS 2017, The Leibniz International Proceedings in Informatics, vol. 66, pp. 46:1-46:14 (2017) · Zbl 1402.68098
[47] Koutecký, M., Levin, A., Onn, S.: A parameterized strongly polynomial algorithm for block structured integer programs. In: Proceedings of ICALP 2018, Leibniz International Proceedings in Informatics, vol. 107, pp. 85:1-85:14 (2018)
[48] Kratsch, S., On polynomial kernels for sparse integer linear programs, J. Comput. Syst. Sci., 82, 5, 758-766 (2016) · Zbl 1338.68111
[49] Lampis, M., Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, 64, 1, 19-37 (2012) · Zbl 1252.68154
[50] Lanctôt, JK; Li, M.; Ma, B.; Wang, S.; Zhang, L., Distinguishing string selection problems, Inf. Comput., 185, 1, 41-55 (2003) · Zbl 1069.68116
[51] Lanctôt, J. Kevin: Some string problems in computational biology. Ph.D. thesis, University of Waterloo (2000)
[52] Lenstra, HW Jr, Integer programming with a fixed number of variables, Math. Oper. Res., 8, 4, 538-548 (1983) · Zbl 0524.90067
[53] Li, M.; Ma, B.; Wang, L., On the closest string and substring problems, J. ACM, 49, 2, 157-171 (2002) · Zbl 1323.68635
[54] Lokshtanov, D.: Parameterized integer quadratic programming: variables and coefficients. Tech. rep. (2015). http://arxiv.org/abs/1511.00310
[55] Ma, B.; Sun, X., More efficient algorithms for closest string and substring problems, SIAM J. Comput., 39, 4, 1432-1443 (2009) · Zbl 1206.68377
[56] Marx, D., Closest substring problems with small distances, SIAM J. Comput., 38, 4, 1382-1410 (2008) · Zbl 1178.68695
[57] Mnich, M.; van Bevern, R., Parameterized complexity of machine scheduling: 15 open problems, Comput. Oper. Res., 100, 254-261 (2018) · Zbl 06938906
[58] Mnich, M.; Wiese, A., Scheduling and fixed-parameter tractability, Math. Program., 154, 533-562 (2015) · Zbl 1332.68089
[59] Niedermeier, R.: Ubiquitous parameterization—invitation to fixed-parameter algorithms. In: Proceedings of MFCS 2004, Lecture Notes in Computer Science, vol. 3153, pp. 84-103 (2004) · Zbl 1096.68068
[60] Nishimura, N., Simjour, N.: Enumerating neighbour and closest strings. In: Proceedings of IPEC 2012, Lecture Notes in Computer Science, vol. 7535, pp. 252-263 (2012) · Zbl 1374.68248
[61] Onn, S.: Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010) · Zbl 1219.90003
[62] Onn, S., Huge multiway table problems, Discrete Optim., 14, 72-77 (2014) · Zbl 1308.90108
[63] Onn, S.; Sarrabezolles, P., Huge unimodular \(n\)-fold programs, SIAM J. Discrete Math., 29, 4, 2277-2283 (2015) · Zbl 1336.90062
[64] Papadimitriou, C.H.: On the complexity of integer programming. J. ACM 28(4) (1981) · Zbl 0468.68050
[65] Stojanovic, N., Berman, P., Gumucio, D., Hardison, R.C., Miller, W.: A linear-time algorithm for the 1-mismatch problem. In: Proceedings of WADS 1997, Lecture Notes in Computer Science, vol. 1272, pp. 126-135 (1997)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.