Re: Theory Tea 2012-2013
Posted: Wed Apr 10, 2013 11:40 pm
Η ομιλία θα γίνει αυτή την Παρασκευή,12/4,5μμ στην Α36XaviannNJ wrote:Επόμενο Theory Tea αύριο!Θα μιλήσει ο Ορέστης Τελέλης.
Ακολουθούν τίτλος και abstract!
Α36,στις 5!Title:
Multi-Unit Combinatorial Auctions with a Few Distinct Goods
Abstract:
We design and analyze deterministic truthful approximation mechanisms
for multi-unit Combinatorial Auctions, with only a constant number of
distinct goods, each in arbitrary limited supply. Prospective buyers
(bidders) have preferences over multisets of items, i.e. for more than
one unit per distinct good. Our objective is to determine allocations
of multisets that (approximately) maximize the Social Welfare. Our
main results are for bidders with multi-minded and submodular
valuation functions. For multi-minded bidders we design a truthful
FPTAS that fully optimizes the Social Welfare, while violating the
supply constraints on goods within factor (1+\epsilon) for any fixed
\epsilon > 0. For submodular bidders we obtain a truthful PTAS,
approximating the optimum Social Welfare within factor (1+\epsilon)
for any fixed \epsilon > 0, without violating the supply constraints.
Our results are best possible and improve and/or generalize upon developments
of [Grandoni et al., ACM SODA 2010] and [Dobzinski, Nisan, JAIR 2010].
This is a joint work with Piotr Krysta (University of Liverpool) and
Carmine Ventre (Teesside University).
Update:Λόγω την κατάληψης η ομιλία θα μεταφερθεί σε μεταγενέστερη ημερομηνία.
