Vi ställer ut tre approximationsalgoritmer för tilldelningsproblem i kombinatoriska auktioner med komplementfria budgivare. Löptiden för dessa algoritmer är polynom i antalet objekt m och i antalet budgivare n, även om "input size" är exponentiellt i m. Den första algoritmen ger en O (log m) approximation. Den andra algoritmen ger en approximation av O( ε m) i den svagare modellen av värde oracles. Denna algoritm är också incitamentskompatibel. Den tredje algoritmen ger en förbättrad 2- approximation för det mer begränsade fallet av "XOS budgivare", en klass som strikt innehåller submodulära budgivare. Vi bevisar också lägre gränser för de möjliga approximationer som kan uppnås för dessa klasser av budgivare. Dessa gränser är inte snäva och vi lämnar luckorna som öppna problem.
Dobzinski m.fl. REF gav en incitamentskombinatorisk auktion för komplementfria budgivare som uppnår en uppskattning av den optimala postens tilldelning.
Approximation algorithms for combinatorial auctions with complement-free bidders
{'venue': "STOC '05", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}