×

Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids. (English) Zbl 1507.68345

Summary: We give a deterministic polynomial-time \(2^{O(r)}\)-approximation algorithm for the number of bases of a given matroid of rank \(r\) and the number of common bases of any two matroids of rank \(r\). To the best of our knowledge, this is the first nontrivial deterministic approximation algorithm that works for arbitrary matroids. Based on a lower bound of Azar, Broder, and Frieze, this is almost the best possible result assuming oracle access to independent sets of the matroid.
There are two main ingredients in our result. For the first, we build upon recent results of Adiprasito, Huh, Katz, and Wang on combinatorial Hodge theory to show that the basis generating polynomial of any matroid is a (completely) log-concave polynomial. Formally, we prove that the multivariate generating polynomial of the bases of any matroid is (and all of its directional derivatives along the positive orthant are) log-concave as functions over the positive orthant. For the second ingredient, we develop a general framework for approximate counting in discrete problems, based on convex optimization. The connection goes through subadditivity of the entropy. For matroids, we prove that an approximate superadditivity of the entropy holds by relying on the log-concavity of the basis generating polynomial.

MSC:

68W25 Approximation algorithms
05B35 Combinatorial aspects of matroids and geometric lattices
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] K. Adiprasito, J. Huh, and E. Katz, Hodge theory for combinatorial geometries, Ann. of Math. (2) 188 (2018), no. 2, 381-452. · Zbl 1442.14194 · doi:10.4007/annals.2018.188.2.1
[2] N. Anari, K. Liu, S. Oveis Gharan, and C. Vinzant, “Log-concave polynomials, II: High-dimensional walks and an FPRAS for counting bases of a matroid” in STOC 2019: 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, 1-12. · Zbl 1433.68606 · doi:10.1145/3313276.3316385
[3] N. Anari, K. Liu, S. Oveis Gharan, and C. Vinzant, Log-concave polynomials, III: Mason’s ultra-log-concavity conjecture for independent sets of matroids, preprint, arXiv:1811.01600v1 [math.CO]. · Zbl 1433.68606
[4] N. Anari and S. Oveis Gharan, “Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP” in FOCS 2015: 56th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, 2015, 20-39. · doi:10.1109/FOCS.2015.11
[5] N. Anari and S. Oveis Gharan, “A generalization of permanent inequalities and applications in counting and optimization” in STOC 2017: 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, 384-396. · Zbl 1370.26031 · doi:10.1145/3055399.3055469
[6] N. Anari, S. Oveis Gharan, and A. Rezaei, “Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes” in COLT 2016: 29th Annual Conference on Learning Theory, Columbia University, New York, 2016, 103-115.
[7] A. Asadpour, M. X. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi, “An \[O(\log n/ \log \log n)\]-approximation algorithm for the asymmetric traveling salesman problem” in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2010, 379-389. · Zbl 1288.05259
[8] Y. Azar, A. Z. Broder, and A. M. Frieze, On the problem of approximating the number of bases of a matriod, Inform. Process. Lett. 50 (1994), no. 1, 9-11. · Zbl 0803.68079 · doi:10.1016/0020-0190(94)90037-X
[9] S. Backman, C. Eur, and C. Simpson, Simplicial generation of Chow rings of matroids, Sém. Lothar. Combin. 84B (2020), art. ID 52. · Zbl 1447.05046
[10] A. Barvinok, Approximate counting via random optimization, Random Structures Algorithms 11 (1997), no. 2, 187-198. · Zbl 0896.60038 · doi:10.1002/(SICI)1098-2418(199709)11:2<187::AID-RSA6>3.0.CO;2-O
[11] A. Barvinok and A. Samorodnitsky, Random weighting, asymptotic counting, and inverse isoperimetry, Israel J. Math. 158 (2007), no. 1, 159-191. · Zbl 1204.60014 · doi:10.1007/s11856-007-0008-8
[12] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge Univ. Press, Cambridge, 2004. · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[13] P. Brändén, Polynomials with the half-plane property and matroid theory, Adv. Math. 216 (2007), no. 1, 302-320. · Zbl 1128.05014 · doi:10.1016/j.aim.2007.05.011
[14] P. Brändén and J. Huh, Lorentzian polynomials, Ann. of Math. (2) 192 (2020), no. 3, 821-891. · Zbl 1454.52013 · doi:10.4007/annals.2020.192.3.4
[15] P. Brändén and J. Huh, Hodge-Riemann relations for Potts model partition functions, preprint, arXiv:1811.01696v2 [math.CO].
[16] Y.-B. Choe, J. G. Oxley, A. D. Sokal, and D. G. Wagner, Homogeneous multivariate polynomials with the half-plane property, Adv. Appl. Math. 32 (2004), no. 1-2, 88-187. · Zbl 1054.05024 · doi:10.1016/S0196-8858(03)00078-2
[17] B. D. Cloteaux, Approximating the number of bases for almost all matroids, Congr. Numer. 202 (2010), 149-154. · Zbl 1229.05063
[18] E. Cohen, P. Tetali, and D. Yeliussizov, Lattice path matroids: Negative correlation and fast mixing, preprint, arXiv:1505.06710v1 [math.CO].
[19] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, Hoboken, 2006. · Zbl 1140.94001
[20] W. H. Cunningham, Testing membership in matroid polyhedra, J. Combin. Theory Ser. B 36 (1984), no. 2, 161-188. · Zbl 0522.90067 · doi:10.1016/0095-8956(84)90023-6
[21] J. Edmonds, Matroids and the greedy algorithm, Math. Program. 1 (1971), 127-136. · Zbl 0253.90027 · doi:10.1007/BF01584082
[22] T. Feder and M. Mihail, “Balanced matroids” in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, B. C., ACM, New York, 1992, 26-38.
[23] A. Gambin, “On approximating the number of bases of exchange preserving matroids” in Mathematical Foundations of Computer Science (Szklarska Poręba, 1999), Lecture Notes in Comput. Sci. 1672, Springer, Berlin, 1999, 332-342. · Zbl 0945.05012
[24] L. GÅrding, An inequality for hyperbolic polynomials, J. Math. Mech. 8 (1959), 957-965. · Zbl 0090.01603 · doi:10.1512/iumj.1959.8.58061
[25] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979. · Zbl 0411.68039
[26] O. Güler, Hyperbolic polynomials and interior point methods for convex programming, Math. Oper. Res. 22 (1997), no. 2, 350-377. · Zbl 0883.90099 · doi:10.1287/moor.22.2.350
[27] L. Gurvits, “Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: Sharper bounds, simpler proofs and algorithmic applications” in STOC 2006: 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, 417-426. · Zbl 1301.90071 · doi:10.1145/1132516.1132578
[28] L. Gurvits, A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor, Discrete Comput. Geom. 41 (2009), no. 4, 533-555. · Zbl 1183.68661 · doi:10.1007/s00454-009-9147-5
[29] L. Gurvits, On Newton (like) inequalities for multivariate homogeneous polynomials, preprint, 2008, http://scholar.lib.vt.edu/MTNS/Papers/042.pdf.
[30] L. Gurvits and A. Samorodnitsky, “Bounds on the permanent and some applications” in FOCS 2014: 55th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, 2014, 90-99. · doi:10.1109/FOCS.2014.18
[31] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge Univ. Press, Cambridge, 2013. · Zbl 1267.15001
[32] J. Huh and B. Wang, Enumeration of points, lines, planes, etc., Acta Math. 218 (2017), no. 2, 297-317. · Zbl 1386.05021 · doi:10.4310/ACTA.2017.v218.n2.a2
[33] H. Imai, S. Iwata, K. Sekine, and K. Yoshida. “Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders” in Computing and Combinatorics (Hong Kong, 1996), Lecture Notes in Comput. Sci. 1090, Springer, Berlin, 1996, 68-80. · Zbl 1529.68184 · doi:10.1007/3-540-61332-3_140
[34] M. Jerrum, Two remarks concerning balanced matroids, Combinatorica 26 (2006), no. 6, 733-742. · Zbl 1121.05027 · doi:10.1007/s00493-006-0039-5
[35] M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM 51 (2004), no. 4, 671-697. · Zbl 1204.65044 · doi:10.1145/1008731.1008738
[36] M. Jerrum and J.-B. Son, “Spectral gap and log-Sobolev constant for balanced matroids” in FOCS 2002: 43rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, 2002, 721-729. · doi:10.1109/SFCS.2002.1181997
[37] M. Jerrum, J.-B. Son, P. Tetali, and E. Vigoda, Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains, Ann. Appl. Probab. 14 (2004), no. 4, 1741-1765. · Zbl 1067.60065 · doi:10.1214/105051604000000639
[38] J. Leake, Capacity preserving operators, preprint, 2018, http://staff.math.su.se/shapiro/IMLConference/Leake.pdf.
[39] N. Linial, A. Samorodnitsky, and A. Wigderson, “A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents” in STOC 1998: 30th Annual ACM Symposium on Theory of Computing, ACM, New York, 1998, 644-652. · Zbl 1027.68980
[40] A. W. Marcus, D. A. Spielman, and N. Srivastava, Interlacing families, I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. (2) 182 (2015), no. 1, 307-325. · Zbl 1316.05066 · doi:10.4007/annals.2015.182.1.7
[41] A. W. Marcus, D. A. Spielman, and N. Srivastava, Interlacing families, II: Mixed characteristic polynomials and the Kadison-Singer problem, Ann. of Math. (2) 182 (2015), no. 1, 327-350. · Zbl 1332.46056 · doi:10.4007/annals.2015.182.1.8
[42] M. Mihail and M. Sudan, Connectivity properties of matroids, preprint, 1991, https://madhu.seas.harvard.edu/papers/1991/matroids.pdf.
[43] M. Mihail and U. Vazirani, On the expansion of \[0/ 1 polytopes \], preprint, 1989.
[44] A. Nikolov and M. Singh, “Maximizing determinants under partition constraints” in STOC 2016: 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, 192-201. · Zbl 1377.90078 · doi:10.1145/2897518.2897649
[45] S. Oveis Gharan, A. Saberi, and M. Singh, “A randomized rounding approach to the traveling salesman problem” in FOCS 2011: 52nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, 2011, 550-559. · Zbl 1292.68171 · doi:10.1109/FOCS.2011.80
[46] A. Schrijver, “Matroid intersection” in Combinatorial Optimization: Polyhedra and Efficiency, Vol. B, Chapter 41, Springer, Berlin, 2003, 700-724. · Zbl 1041.90001
[47] A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82 (1989), no. 1, 93-133. · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9
[48] M. Singh and N. K. Vishnoi, “Entropy, optimization and counting” in STOC 2014: 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, 50-59. · Zbl 1315.94027 · doi:10.1145/2591796.2591803
[49] M. Snook, Counting bases of representable matroids, Electron. J. Combin. 19 (2012), no. 4, art. ID 41. · Zbl 1267.05058
[50] D. Straszak and N. K. Vishnoi, “Real stable polynomials and matroids: Optimization and counting” in STOC 2017: 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, 370-383. · Zbl 1370.90180 · doi:10.1145/3055399.3055457
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.