Vi presenterar de första polynom-tids approximationsalgoritmerna för ensinnade avundsfria vinstmaximeringsproblem [13] med begränsad tillgång. Våra algoritmer returnerar ett prissättningssystem och en undergrupp av kunder som utses vinnarna, som uppfyller avunds-frihetsbegränsningen, medan vi i våra analyser jämför vinsten av vår lösning mot det optimala värdet av motsvarande social-välfärd-maximering (SWM) problem att hitta en vinnare-uppsättning med maximalt totalt värde. Våra algoritmer tar alla LP-baserade α-tillnärmning algoritm för motsvarande SWM-problem som ingång och returnera en lösning som uppnår vinst minst OPT /O(α · log u max ), där OPT är det optimala värdet av SWM-problemet, och u max är den maximala tillgången på en produkt. Detta ger omedelbart ungefärliga garantier för O( ε m log u max ) för det allmänna ensinnade avundsfria problemet; och O(log u max ) för avgifts- och motorvägsproblem [13], och graf-vertex prisproblem [3] (α = O(1) för alla motsvarande SWM-problem). Eftersom OPT är en övre gräns för den maximala vinst som kan uppnås genom någon lösning (dvs. oavsett om lösningen uppfyller avundsfrihetsbegränsningen), för våra resultat direkt över till de icke-avundsfria versionerna av dessa problem också. Vårt resultat etablerar också (konstruktivt) en övre gräns för O(α · log u max ) på förhållandet mellan (i) det optimala värdet av problemet med vinstmaximering och OPT ; och (ii) den optimala vinst som kan uppnås med och utan begränsningen av avundsfrihet.
Cheung och Swamy studerade den avundsfria varianten av kapacierade prissättningsproblem REF.
Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply
{'venue': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}