Vi ger en deterministisk polynom tid 2 O (r) approximation algoritm för antalet baser av en given matris av rank r och antalet gemensamma baser av två matriser av rank r. Till det bästa av vår kunskap, är detta den första icke-triviala deterministiska approximation algoritm som fungerar för godtyckliga matriser. Baserat på en nedre gräns av Azar, Broder och Frieze [7] är detta nästan det bästa möjliga antagandet oraklet tillgång till oberoende uppsättningar av matroiden. Det finns två huvudingredienser i vårt resultat: För det första bygger vi på de senaste resultaten av Adiprasito, Huh, och Katz [1] och Huh och Wang [23] på kombinatorisk Hodge teori för att härleda en koppling mellan matroider och logconcave polynomials. Vi förväntar oss att flera nya applikationer i approximationsalgoritmer kommer att härledas från detta samband i framtiden. Formellt, Vi bevisar att multivariat generera polynom av baserna i någon matroid är logconcave som en funktion över den positiva ortanthant. För den andra ingrediensen utvecklar vi en allmän ram för ungefärlig beräkning av diskreta problem, baserad på konvex optimering. Anslutningen går genom subadditivitet av entropi. För matroider, vi bevisar att en ungefärlig superadditivitet av entropi håller genom att förlita sig på log-koncavity av motsvarande polynomials.
I REF, en delmängd av författarna gav en deterministisk e r approximation till antalet baser med hjälp av det faktum att  på μ (M) är log-concave över R n 0.
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
{'venue': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}