Abstract-Det har nyligen observerats att permanent av en icke-negativ fyrkantig matris, dvs., av en fyrkantig matris som endast innehåller icke-negativa verkliga poster, mycket väl kan approximeras genom att lösa en viss Bete fri energi funktion minimering problem med hjälp av summan-produkt algoritm. Vi kallar den resulterande approximationen av den permanenta Bethe permanent. I detta dokument ger vi anledning till varför denna metod för att tillnärma de permanenta fungerar bra. Nämligen visar vi att Bethes fria energifunktion är konvex och att totalproduktalgoritmen finner sitt minimum effektivt. Vi diskuterar sedan det faktum att det permanenta är lägre avgränsat av Bethe permanent, och vi kommenterar potentiella övre gränser på det permanenta baserat på Bethe permanent. Vi presenterar också en kombinatorisk karakterisering av Bethe permanent i termer av permanenta av så kallade upplyfta versioner av den matris som övervägs. Dessutom kommenterar vi möjligheterna att ändra Bethe permanent så att det approximerar det permanenta ännu bättre, och vi avslutar dokumentet med några observationer och gissningar om permanent-baserade pseudokodord och permanent-baserade kärnor.
Det har observerats REF att till skillnad från i det allmänna fallet, för permanenta program (2.4) är konvex.
The Bethe Permanent of a Nonnegative Matrix
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}