Eastern Great Lakes Theory Workshop Talk

Linear and Monotone Submodular Optimization in k-Exchange

Justin Ward, University of Toronto

Saturday, September 10, 5:00-5:20pm

ABSTRACT

We present a class of hereditary independence systems called k-exchange systems. These systems generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. Such problems include matroid k-parity in strongly base orderable matroids, independent set in (k + 1)-claw free graphs (which includes k-set packing as a special case), b-matching (k = 2), and maximum asymmetric traveling salesperson (k = 3). We consider the general problem of maximizing a set function f over a given k-exchange system, and give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of (k + 1)/2 in the case that f is linear and (k + 3)/2 in the case that f is monotone submodular.

Speaker Bio

Justin Ward received his BS in Computer Science from the University of Kansas and an MSc from the University of Toronto, in the area of formal methods for software engineering and algorithm design. He is currently pursuing a PhD at the University of Toronto, with a focus on algorithm design and analysis. His research interests include analysis and design local search algorithms for approximation, submodular optimization, and independence systems.

< Schedule < EaGL-IV homepage