Breaking symmetries to rescue sum of squares in the case of makespan scheduling
Tóm tắt
The sum of squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of this hierarchy give integrality gaps matching the best known approximation algorithms. For many other problems, however, ad-hoc techniques give better approximation ratios than SoS in the worst case, as shown by corresponding lower bound instances. Notably, in many cases these instances are invariant under the action of a large permutation group. This yields the question how symmetries in a formulation degrade the performance of the relaxation obtained by the SoS hierarchy. In this paper, we study this for the case of the minimum makespan problem on identical machines. Our first result is to show that
$$\varOmega (n)$$
rounds of SoS applied over the configuration linear program yields an integrality gap of at least 1.0009, where n is the number of jobs. This improves on the recent work by Kurpisz et al. (Math Program 172(1–2):231–248, 2018) that shows an analogous result for the weaker
$$\hbox {LS}_{+}$$
and SA hierarchies. Our result is based on tools from representation theory of symmetric groups. Then, we consider the weaker assignment linear program and add a well chosen set of symmetry breaking inequalities that removes a subset of the machine permutation symmetries. We show that applying
$$2^{\tilde{O}(1/\varepsilon ^2)}$$
rounds of the
$$\text {SA}$$
hierarchy to this stronger linear program reduces the integrality gap to
$$1+\varepsilon $$
, which yields a linear programming based polynomial time approximation scheme. Our results suggest that for this classical problem, symmetries were the main barrier preventing the
$$\text {SoS}/\text {SA}$$
hierarchies to give relaxations of polynomial complexity with an integrality gap of
$$1+\varepsilon $$
. We leave as an open question whether this phenomenon occurs for other symmetric problems.
Tài liệu tham khảo
Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 493–500 (1997)
Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55–66 (1998)
Askey, R.: Orthogonal polynomials and special functions. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol 21. SIAM (1975)
Au, Y.H.G., Tunçel, L.: Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators. Discrete Optim. 27, 103–129 (2018)
Barak, B., Chan, S.O., Kothari, P.K.: Sum of squares lower bounds from pairwise independence. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp. 97–106 (2015)
Barak, B., Hopkins, S.B., Kelner, J., Kothari, P., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. In: Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 428–437 (2016)
Barak, B., Moitra, A.: Noisy tensor completion via the sum-of-squares hierarchy. In: Proceedings of the 29th Conference on Learning Theory (COLT), pp. 417–445 (2016)
Blekherman, G., Gouveia, J., Pfeiffer, J.: Sums of squares on the hypercube. Math. Z. 284(1–2), 41–54 (2016)
Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp 139–169. Springer, Belin (2012)
Cox, D.A., Little, J.B., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (2007)
Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 808–816 (2018)
Garg, S.: Quasi-PTAS for scheduling with precedences using LP hierarchies. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 59:1–59:13 (2018)
Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra 192(1–3), 95–128 (2004)
Goemans, M., Rothvoß, T.: Polynomiality for bin packing with a constant number of item types. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 830–839 (2014)
Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM 42, 1115–1145 (1995)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563–1581 (1966)
Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Comput. Complex. 10(2), 139–154 (2001)
Grigoriev, D.: Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theor. Comput. Sci. 259(1–2), 613–622 (2001)
Hochbaum, D.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Co., Boston (1996)
Hochbaum, D., Shmoys, D.: Using dual approximation algorithms for scheduling problems theoretical and practical results. JACM 34, 144–162 (1987)
Hopkins, S.B., Kothari, P.K., Potechin, A., Raghavendra, P., Schramm, T., Steurer, D.: The power of sum-of-squares for detecting hidden structures. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 720–731 (2017)
Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables. SIAM J. Discrete Math. 24(2), 457–485 (2010)
Jansen, K., Klein, K., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 72:1–72:13 (2016)
Karlin, A., Mathieu, C., Nguyen, C.: Integrality gaps of linear and semi-definite programming relaxations for knapsack. In: Proceedings of the 15th International Conference on Integer Programming and Combinatoral Optimization (IPCO), pp. 301–314. (2011)
Kothari, P., O’Donnell, R., Schramm, T.: SOS lower bounds with hard constraints: think global, act local. arXiv:1809.01207 (2018)
Kothari, P.K., Mori, R., O’Donnell, R., Witmer, D.: Sum of squares lower bounds for refuting any CSP. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 132–145 (2017)
Kothari, P.K., Steinhardt, J., Steurer, D.: Robust moment estimation and improved clustering via sum of squares. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1035–1046 (2018)
Kurpisz, A., Leppänen, S., Mastrolilli, M.: On the hardest problem formulations for the 0/1 lasserre hierarchy. Math. Oper. Res. 42(1), 135–143 (2016)
Kurpisz, A., Leppänen, S., Mastrolilli, M.: Sum of squares hierarchy lower bounds for symmetric formulations. In: Proceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 362–374 (2016)
Kurpisz, A., Leppänen, S., Mastrolilli, M.: An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem. Math. Program. 166(1–2), 1–17 (2017)
Kurpisz, A., Mastrolilli, M., Mathieu, C., Mömke, T., Verdugo, V., Wiese, A.: Semidefinite and linear programming integrality gaps for scheduling identical machines. Math. Program. 172(1–2), 231–248 (2018)
Lasserre, J.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)
Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28, 470–496 (2003)
Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4), 871–883 (2003)
Laurent, M.: Semidefinite representations for finite varieties. Math. Program. 109(1), 1–26 (2007)
Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157–270. Springer, New York (2009)
Levey, E., Rothvoss, T.: A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 168–177 (2016)
Ma, T., Shi, J., Steurer, D.: Polynomial-time tensor decompositions with sum-of-squares. In: Foundations of Computer Science (FOCS), pp. 438–446 (2016)
Margot, F.: Symmetry in integer linear programming. In: 50 Years of Integer Programming 1958–2008. Springer, Berlin (2010)
Mastrolilli, M.: High degree sum of squares proofs, Bienstock–Zuckerberg hierarchy and cg cuts. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 405–416. Springer, New York (2017)
Parrilo, P.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293–320 (2003)
Potechin, A.: Sum of squares lower bounds from symmetry and a good story. arXiv:1711.11469 (2017)
Potechin, A., Steurer, D.: Exact tensor completion with sum-of-squares. arXiv:1702.06237 (2017)
Raghavendra, P., Schramm, T., Steurer, D.: High-dimensional estimation via sum-of-squares proofs. arXiv:1807.11419 (2018)
Raymond, A., Saunderson, J., Singh, M., Thomas, R.R.: Symmetric sums of squares over k-subset hypercubes. Math. Program. 167(2), 315–354 (2018)
Razborov, A.A.: Flag algebras. J. Symb. Log. 72(4), 1239–1282 (2007)
Razborov, A.A.: On 3-hypergraphs with forbidden 4-vertex configurations. SIAM J. Discrete Math. 24(3), 946–963 (2010)
Rothvoß, T.: The Lasserre hierarchy in approximation algorithms. Lecture notes for MAPSP (2013)
Sagan, B.: The Symmetric Group. Graduate Texts in Mathematics. Springer, New York (2001)
Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPS. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 593–602 (2008)
Sherali, H., Adams, W.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411–430 (1990)
Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41(5), 1318–1341 (2012)
Verdugo, V., Verschae, J.: Breaking symmetries to rescue sum of squares: the case of makespan scheduling. In: 20th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2019), pp. 427–441 (2019)
Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)