[Nets-seminars] Final talk of term Friday 1st July GS/302 16:00

[Richard G. Clegg]

Our final talk of term (next Friday) is a guest speaker from Liverpool, 
Piotr Krysta.

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.

This is joint work with Fabrizio Grandoni, Stefano Leonardi and Carmine Ventre.


-- 
Richard G. Clegg,
Dept of Elec. Eng.,
University College London
http://www.richardclegg.org/