Extended formulations from communication protocols in output-efficient time
Tóm tắt
Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the extended formulation also depends on the number of rows of the slack matrix (hence, on the exact description in the original space). We give general sufficient conditions under which those tools can be implemented as to be output-efficient, showing applications to e.g. Yannakakis’ extended formulation for the stable set polytope of perfect graphs, for which, to the best of our knowledge, an efficient construction was previously not known. For specific classes of polytopes, we give also a direct, efficient construction of extended formulations arising from protocols. Finally, we deal with extended formulations coming from unambiguous non-deterministic protocols.
Tài liệu tham khảo
Aprile, M.: On some problems related to 2-level polytopes. PhD thesis, École Polytechnique Fédérale de Lausanne (2018)
Aprile, M., Faenza, Y.: Extended formulations from communication protocols in output-efficient time. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 43–56. Springer (2019)
Aprile, M., Faenza, Y., Fiorini, S., Huynh, T., Macchia, M.: Extension complexity of stable set polytopes of bipartite graphs. In: CONF, vol. 10520, pp. 75–87. Springer, Cham (2017)
Balas, E.: Disjunctive programming. Ann. Discret. Math. 5, 3–51 (1979)
Bazzi, A., Fiorini, S., Huang, S., Svensson, O.: Small extended formulation for knapsack cover inequalities from monotone circuits . In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2326–2341. SIAM (2017)
Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor \(2- \epsilon \). Math. Oper. Res. 44(1), 147–172 (2018)
Bousquet, N., Lagoutte, A., Thomassé, S.: Clique versus independent set. Eur. J. Comb. 40, 73–92 (2014). https://doi.org/10.1016/j.ejc.2014.02.003
Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. J. ACM (JACM) 63(4), 34 (2016)
Chudnovsky, M., Trotignon, N., Trunck, T., Vušsković, K.: Coloring perfect graphs with no balanced skew-partitions. J. Comb. Theory Ser. B 115, 26–65 (2015)
Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory Ser. B 18, 138–154 (1975)
Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8(1), 1–48 (2010)
Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. Math. Program. 153(1), 75–94 (2015)
Faenza, Y., Oriolo, G., Stauffer, G.: Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1298–1308. Society for Industrial and Applied Mathematics (2012)
Faenza, Y., Oriolo, G., Stauffer, G.: Separation routine and extended formulations for the stable set problem in claw-free graphs. In: Mathematical Programming (2020)
Fiorini, S., Huynh, T., Weltge, S.: Strengthening convex relaxations of 0/1-sets using Boolean formulas. arXiv:1711.01358 (2017)
Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 95–106. ACM (2012)
Göös, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. SIAM J. Comput. 47(1), 241–269 (2018)
Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Berge, C., Chvátal, V. (eds.) North-Holland Mathematics Studies, vol. 88, pp. 325–356. Elsevier, Amsterdam (1984)
Håstad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798–859 (2001)
Kaibel, V.: Extended formulations in combinatorial optimization. OPTIMA 85, 2–7 (2011)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1996)
Lagoutte, A.: Personal communication (2018)
Lee, J., Leung, J., Margot, F.: Min-up/min-down polytopes. Discret. Optim. 1(1), 77–85 (2004)
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1–7 (1979)
Pashkovich, K.: Extended formulations for combinatorial polytopes. PhD thesis, Otto-von-Guericke-Universität Magdeburg (2012)
Rajan, D., Takriti, S.: Minimum up/down polytopes of the unit commitment problem with start-up costs. IBM Res. Rep. RC 23628, 1–14 (2005)
Rao, A., Yehudayoff, A.: Communication Complexity: and Applications. Cambridge University Press (2020)
Rothvoß, T.: The matching polytope has exponential extension complexity. J. ACM (JACM) 64(6), 41 (2017)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2002)
Weltge, S.: Sizes of linear descriptions in combinatorial optimization. PhD thesis, Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik (2015)
Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43, 441–466 (1991)