Budget genomförbara mekanismer, nyligen initierad av Singer, utvidga algoritmiska mekanism design problem till en realistisk inställning med en budget begränsning. Vi betraktar problemet med att utforma sanningsenliga budgetgenomförbara mekanismer för submodulära monotona funktioner: Vi ger en randomiserad mekanism med en approximationsgrad på 7,91 (förbättring av det tidigare mest kända resultatet 233,83) och en deterministisk mekanism med en approximationsgrad på 8,34. Vi studerar också Knapsack-problemet, som är en speciell submodulär funktion, ger en 2 + 2 approximation deterministisk mekanism (förbättrar på den tidigare mest kända resultat 5), och en 3 approximation randomiserade mekanism. Vi ger liknande resultat för en utökad ryggsäck problem med heterogena objekt, där objekt är uppdelade i grupper och man kan välja som mest ett objekt från varje grupp. Slutligen visar vi en lägre gräns på 1 + 2 för approximation av deterministiska mekanismer och 2 för randomiserade mekanismer för knapsack, liksom den allmänna monotona submodulära funktioner. Våra nedre gränser är ovillkorliga och förlitar sig inte på några beräknings- eller komplexitetsantaganden.
Förbättrar ett tidigare resultat av Singer, Chen et al. REF ger en sanningsenlig, 2 + 2 ungefärlig mekanism för Knapsack, och en nedre gräns på 1 + 2.
On the approximability of budget feasible mechanisms
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}