[Nets-seminars] Final talk of term this Friday 24th June GS/302
16:00
Richard G. Clegg
richard at richardclegg.org
Thu Jun 23 15:56:25 BST 2011
Our final talk of term is tomorrow. Apologies for the incorrect date on
the previous email. The talk is this week on 24th of June, NOT 1st July
as previously posted.
Title: Utilitarian Mechanism Design for Multi-objective Optimization
Piotr Krysta, Department of Computer Science, University of Liverpool, UK
Abstract:
We study mechanism design for NP-hard multi-objective optimization
problems with one objective function and secondary objectives modelled
by budget constraints. Our main contribution is showing that two of the
main tools for the design of approximation algorithms for
multi-objective optimization problems, approximate Pareto curves and
Lagrangean relaxation, can lead to truthful approximation schemes. By
exploiting the first method, we devise truthful FPTASs for the
multi-budgeted versions of minimum spanning tree, shortest path, maximum
matching, and matroid intersection problems. By building on the second
method, we present a universally truthful Las Vegas PTAS for the minimum
spanning tree problem with a single budget constraint, without violating
the budget constraint. Our achieved approximation guarantees match the
best known approximation guarantees for the respective problems, which,
however, were obtained by non-truthful algorithms. In this talk I will
focus on the
minimum spanning tree problem with a single budget constraint.
--
Richard G. Clegg,
Dept of Elec. Eng.,
University College London
http://www.richardclegg.org/
More information about the Nets-seminars
mailing list