Vi betraktar problemet med MaxMin tilldelning av odelbara varor. Det finns m objekt som ska fördelas bland n spelare. Varje spelare i har en icke-negativ värdering p i j för en post j, och målet är att fördela objekt till spelare för att maximera den minsta totala värderingen som varje spelare får. Det finns en stor lucka i vår förståelse av detta problem. Det mest kända positiva resultatet är en Õ( ε n)-tillnärmningsalgoritm, medan det bara finns en faktor 2 hårdhet känd. Bättre algoritmer är kända för den begränsade tilldelning fall där varje objekt har exakt ett nonzero värde för spelarna. Vi studerar effekten av begränsad grad för objekt: varje objekt har ett nonzero värde för som mest D-spelare. Vi visar att i huvudsak fallet D = 3 är likvärdigt med det allmänna fallet, och ger en 4- approximationsalgoritm för D = 2. De aktuella algoritmiska resultaten för MaxMin Allocation är baserade på en komplicerad LP-avslappning som kallas konfigurationen LP. Vi presenterar en mycket enklare LP som är likvärdig i kraft till konfiguration LP. Vi fokuserar på ett specialfall av MaxMin Allocationa familj av fall där denna LP har ett polynomiskt stort gap. Den tekniska kärnan i vårt resultat för detta fall kommer från en algoritm för en intressant ny optimering problem på riktade grafer, MaxMinDegree Arborescence, där målet är att producera en arborescens av stora utgrader. Vi utvecklar en n ε - approximation för detta problem som körs i n O(1/ε) tid och få en polylogaritmisk approximation som körs i kvasipolynom tid, med hjälp av en lyft-och-projekt inspirerad LP formulering. I själva verket * En fullständig version av detta dokument finns som en teknisk rapport [5]. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Vi visar att våra resultat innebär en avrundningsalgoritm för de avslappningar som uppnås genom t rundor i Sherali-Adams hierarki tillämpas på en naturlig LP avslappning av problemet. Grovt taget är integrality gapet i den avslappning som erhålls från t rundor av SheraliAdams som mest n 1/t. Vi kan utvidga det senare resultatet till en mer allmän typ av fall. Längs vägen visar vi ett resultat om existensen av en perfekt matchning i en probabilistiskt beskurna graf som kan vara av oberoende intresse.
I REF anser författarna att varje objekt har en positiv nytta för ett begränsat antal spelare D, och bevisar att problemet är lika svårt som det allmänna fallet för D 3.
MaxMin allocation via degree lower-bounded arborescences
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}