On Integer Programming, Discrepancy, and Convolution

References

• [1] Abboud A, Bringmann K, Hermelin D, Shabtay D (2022) SETH-based lower bounds for subset sum and bicriteria path. (ACM) Trans. Algorithms 18(1):6:1–6:22.Google Scholar
• [2] Agarwal PK, Sharir M, Toledo S (1993) An efficient multi-dimensional searching technique and its applications. Technical Report CS-1993-20, Duke University, Durham.Google Scholar
• [3] Axiotis K, Tzamos C (2019) Capacitated dynamic programming: Faster knapsack and graph algorithms. Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, eds. Proc. ICALP, vol. 19 (Schloss Dagstuhl, Patras, Greece), 1–13.Google Scholar
• [4] Backurs A, Indyk P, Schmidt L (2017) Better approximations for tree sparsity in nearly-linear time. Klein PN, ed. Proc. SODA (SIAM, Barcelona, Spain), 2215–2229.Google Scholar
• [5] Bansal N (2010) Constructive algorithms for discrepancy minimization. Proc. FOCS (IEEE, Las Vegas), 3–10.Google Scholar
• [6] Beck J, Fiala T (1981) “Integer-making” theorems. Discrete Appl. Math. 3(1):1–8.Crossref, Google Scholar
• [7] Berndt S, Deppert MA, Jansen K, Rohwedder L (2022) Load balancing: The long road from theory to practice. Phillips CA, Speckmann B, eds. Proc. ALENEX (SIAM, Alexandria), 104–116.Google Scholar
• [8] Bremner D, Chan TM, Demaine ED, Erickson J, Hurtado F, Iacono J, Langerman S, Patrascu M, Taslakian P (2014) Necklaces, convolutions, and X+Y. Algorithmica 69(2):294–314.Crossref, Google Scholar
• [9] Bringmann K (2017) A near-linear pseudopolynomial time algorithm for subset sum. Klein PN, ed. Proc. SODA (SIAM, Barcelona, Spain), 1073–1084.Google Scholar
• [10] Brönnimann H, Chazelle B, Matousek J (1999) Product range spaces, sensitive sampling, and derandomization. SIAM J. Comput. 28(5):1552–1575.Crossref, Google Scholar
• [11] Chan TM (2018) Improved deterministic algorithms for linear programming in low dimensions. ACM Trans. Algorithms 14(3):1–10.Crossref, Google Scholar
• [12] Chan TM, He Q (2022) More on change-making and related problems. J. Comput. System Sci. 124:159–169.Crossref, Google Scholar
• [13] Chan TM, Lewenstein M (2015) Clustered integer 3SUM via additive combinatorics. Servedio RA, Rubinfeld R, eds. Proc. STOC (ACM, Portland), 31–40.Google Scholar
• [14] Chazelle B, Matousek J (1996) On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21(3):579–597.Crossref, Google Scholar
• [15] Clarkson KL (1986) Linear programming in O(n×3d2) time. Inform. Processing Lett. 22(1):21–24.Crossref, Google Scholar
• [16] Clarkson KL (1995) Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2):488–499.Crossref, Google Scholar
• [17] Cygan M, Mucha M, Wegrzycki K, Wlodarczyk M (2019) On problems equivalent to (min, +)-convolution. (ACM) Trans. Algorithms 15(1):14:1–14:25.Google Scholar
• [18] Dadush D (2012) Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation (Georgia Institute of Technology, Atlanta).Google Scholar
• [19] Dadush D (2014) A randomized sieving algorithm for approximate integer programming. Algorithmica 70(2):208–244.Crossref, Google Scholar
• [20] Dyer ME (1986) On a multidimensional search technique and its application to the Euclidean one-centre problem. SIAM J. Comput. 15(3):725–738.Crossref, Google Scholar
• [21] Dyer ME, Frieze AM (1989) A randomized algorithm for fixed-dimensional linear programming. Math. Programming 44(1–3):203–212.Crossref, Google Scholar
• [22] Eisenbrand F, Weismantel R (2020) Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms 16(1):1–14.Crossref, Google Scholar
• [23] Fomin FV, Panolan F, Ramanujan MS, Saurabh S (2018) On the optimality of pseudo-polynomial algorithms for integer programming. Azar Y, Bast H, Herman G, eds. Proc. ESA 2018, vol. 31 (Schloss Dagstuhl, Helsinki, Finland), 1–13.Google Scholar
• [24] Jansen K, Rohwedder L (2019) On integer programming and convolution. Blum A, ed. Proc. ITCS, vol. 43 (Schloss Dagstuhl, San Diego), 1–17.Google Scholar
• [25] Jansen K, Klein K, Verschae J (2020) Closing the gap for makespan scheduling via sparsification techniques. Math. Oper. Res. 45(4):1371–1392.Link, Google Scholar
• [26] Kalai G (1992) A subexponential randomized simplex algorithm (extended abstract). Kosaraju SR, Fellows M, Wigderson A, Ellis JA, eds. Proc. STOC (ACM, Victoria, Canada), 475–482.Google Scholar
• [27] Kannan R (1987) Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3):415–440.Link, Google Scholar
• [28] Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer).Crossref, Google Scholar
• [29] Klein KM (2022) On the fine-grained complexity of the unbounded subsetsum and the Frobenius problem. Naor JS, Buchbinder N, eds. Proc. SODA (SIAM, Alexandria), 3567–3582.Google Scholar
• [30] Knop D, Pilipczuk M, Wrochna M (2020) Tight complexity lower bounds for integer linear programming with few constraints. (ACM) Trans. Comput. Theory 12(3):19:1–19:19.Google Scholar
• [31] Künnemann M, Paturi R, Schneider S (2017) On the fine-grained complexity of one-dimensional dynamic programming. Chatzigiannakis I, Indyk P, Kuhn F, Muscholl A, eds. Proc. ICALP, vol. 21 (Schloss Dagstuhl, Warsaw, Poland), 1–15.Google Scholar
• [32] Laber ES, Roncalla WB, Cicalese F (2014) On lower bounds for the maximum consecutive subsums problem and the (min, +)-convolution. Proc. ISIT (IEEE, Honolulu), 1807–1811.Google Scholar
• [33] Lenstra HW (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [34] Lovász L, Spencer J, Vesztergombi K (1986) Discrepancy of set-systems and matrices. Eur. J. Combin. 7(2):151–160.Crossref, Google Scholar
• [35] Lovett S, Meka R (2015) Constructive discrepancy minimization by walking on the edges. SIAM J. Comput. 44(5):1573–1582.Crossref, Google Scholar
• [36] Matousek J, Sharir M, Welzl E (1996) A subexponential bound for linear programming. Algorithmica 16(4/5):498–516.Crossref, Google Scholar
• [37] Megiddo N (1984) Linear programming in linear time when the dimension is fixed. J. ACM 31(1):114–127.Crossref, Google Scholar
• [38] Papadimitriou CH (1981) On the complexity of integer programming. J. ACM 28(4):765–768.Crossref, Google Scholar
• [39] Seidel R (1991) Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geometry 6:423–434.Crossref, Google Scholar
• [40] Sevastyanov SV (1978) Approximate solution of some problems in scheduling theory. Metody Diskretnogo Analiza. 32:66–75.Google Scholar
• [41] Spencer J (1985) Six standard deviations suffice. Trans. Amer. Math. Soc. 289(2):679–706.Crossref, Google Scholar
• [42] Steinitz E (1913) Bedingt konvergente reihen und konvexe systeme. Journal für die Reine und Angewandte Mathematik 143:128–176.Crossref, Google Scholar