Problemet med hypergrafmatchning är att hitta en största samling osammanhängande hyperkanter i en hypergraf. Detta är ett välstuderat problem i kombinatorisk optimering och grafteori med olika tillämpningar. De mest kända approximationsalgoritmerna för detta problem är alla lokala sökalgoritmer. I detta papper analyserar vi olika linjära och semidefinita programmeringsavkopplingar för hypergraph matchningsproblem, och studerar deras kopplingar till den lokala sökmetoden. Våra viktigaste resultat är följande: • Vi anser att den normala linjära programmering av problemet. Vi tillhandahåller ett algoritmiskt bevis på ett resultat av Füredi, Kahn och Seymour, som visar att integralititetsgapet är exakt k − 1 + 1/k för k-uniform hypergraphs, och är exakt k − 1 för k-partit hypergraphs. Detta ger en förbättrad approximationsalgoritm för det viktade 3-dimensionella matchningsproblemet. Vår algoritm kombinerar användningen av den iterativa avrundningsmetoden och metoden med fraktionerat lokalt förhållande, vilket visar ett nytt sätt att runda linjära programmeringslösningar för förpackningsproblem. • Vi studerar förstärkningen av standard LP avslappning genom lokala begränsningar. Vi visar att även efter linjärt antal rundor av Sherali-Adams lyft-och projektprocedur på standard LP relaxation, det finns k-uniform hypergraphs med integrality gap minst k − 2. Å andra sidan visar vi att för varje konstant k, det finns en förstärkning av standard LP avslappning med bara ett polynom antal begränsningar, med integrality gap som mest (k + 1)/2 för k-uniform hypergraphs. Konstruktionen använder ett resultat i extrem kombinatorik. • Vi anser att den vanliga halvdefinita programmeringen av problemet är avslappning. Vi visar att Lovász-funktionen ger en SDP-avkoppling med integrality gap som mest (k + 1)/2. Beviset ger ett indirekt sätt (inte genom en avrundningsalgoritm) att begränsa förhållandet mellan en lokal optimal lösning och en optimal SDP-lösning. Detta visar en ny koppling mellan lokal sökning och linjära och semidefinita programmeringsavkopplingar.
I en viktig riktning av forskning Chan och Lau REF överväga kraften av linjära och semidefinita avkopplingar för k-Set Packing problem.
On linear and semidefinite programming relaxations for hypergraph matching
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}