Vi får en uppsättning kunder med budgetbegränsningar och en uppsättning odelbara poster. Varje klient är villig att köpa en eller flera buntar av (som mest) k objekt varje (bundlar kan ses som överkanter i en k-hypergraph). Om kunden jag får en bunt e, betalar hon b i,e och ger en nettovinst w i,e. Hypermatching Uppdragsproblem (HAP) är att tilldela en uppsättning pairwise osammanhängande paket till kunder för att maximera den totala vinsten samtidigt som budgeten. Detta problem har olika tillämpningar i produktionsplanering och budget-konstruerade auktioner och generaliserar välstuderade problem i kombinatorisk optimering: till exempel den viktade (oviktade) khypergraph matchning problem är det speciella fallet med HAP med en klient som har obunden budget och allmänna (enhet) vinster; Generalized Inmission Problem (GAP) är det speciella fallet med HAP med k = 1. Låt ε > 0 betecknar en godtyckligt liten konstant. I detta papper får vi följande huvudsakliga resultat: • Vi ger en randomiserad (k + 1 + ) approximation algoritm för HAP, som bygger på avrundning 1-round Lasserre förstärkning av en ny LP. Detta är ett av några approximativa resultat baserat på Lasserre hierarkier och vår strategi kan vara av oberoende intresse. Vi noterar att för viktad k-hypergraph som inte matchar någon LP eller SDP avslappning är känt för att ha integrality gap bättre än k − 1 + 1/k för allmänna k [Chan och Lau, SODA'10]. • För relevant specialfall som man vill maximera den totala intäkten (dvs. b i,e = w i,e ), presenterar vi en lokal sökning baserad (k + O ( ε k))/2 approximationsalgoritm för k = O(1). Detta motsvarar nästan det mest kända (k + 1 + )/2 approximationsförhållandet av Berman [SWAT'00] för *
MaxkSP problemet är relaterat till den nyligen studerade hypermatching uppdragsproblem (HAP) REF, och specialfall, inklusive k-set förpackning, och en enhetlig version av problemet.
How to Sell Hyperedges: The Hypermatching Assignment Problem
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}