Maximising Bisubmodular and k-Submodular Functions
- 16:00 12th November 2013 ( week 5, Michaelmas Term 2013 )Room 278, Oxford e-Research Centre, 7 Keble Road
Submodular functions play a key role in combinatorial optimisation and in the theory of valued constraint satisfaction problems. Recently, there has been interest in various generalisations of submodularity, including bisubmodular functions, which operate on disjoint pairs of sets, rather than single sets. Like submodular functions, bisubmodular functions can be minimised exactly in polynomial time and exhibit the property of diminishing returns. In this talk, I will present recent joint work with Stanislav Zivny on maximising both bisubmodular functions and also general k-submodular functions, which operate on disjoint k-tuples of sets. Additionally, I will discuss the relationship between bisubmodularity and submodularity, and show how our results on bisubmodular functions can provide intuition for existing algorithms that maximise submodular functions, such as the recent 1/2-approximation algorithm of Buchbinder, Feldman, Naor, and Schwarz.
Speaker bio
Justin Ward is a Research Fellow in the Department of Computer Science and the Centre for Discrete Mathematics and its Applications at the University of Warwick. He recently completed his Ph.D. in computer science at the University of Toronto under the supervision of Allan Borodin, and holds undergraduate degrees in both computer science and English literature from the University of Kansas. His primary research interests lie in the area of theoretical computer science, in particular in the design and analysis of approximation algorithms. His most recent research has been in the area of constrained, submodular maximisation, with a specific focus on the design and analysis of local search algorithms. More generally, he is interested in theoretical models of simple algorithmic paradigms, with the goal of obtaining information theoretic limits on the performance of large classes of algorithms.Share this:
