Please note: This seminar will take place in DC 1304 and online.
David Wajc, Professor
The Technion
We introduce the submodular objectives chasing problem, which generalizes many natural and previously-studied problems: a sequence of constrained submodular maximization problems is revealed over time, with both the objective and available ground set changing over time. The goal is to maintain solutions of high approximation and low total recourse (number of changes), compared with exact offline algorithms for the same input sequence. For the central cardinality constraint and partition matroid constraints we provide optimal (1 − 1/e − ε)-approximation in polynomial time, with competitive recourse that is best-possible for any constant-approximation.
Along the way, we design a new meta-algorithm for (1 − 1/e − ε)-approximately maximizing the multilinear extension under general constraints, which we call approximate-or-separate. The algorithm, whose guarantees are similar to the influential continuous greedy algorithm [Calinescu-Chekuri-Pál-Vondrák SICOMP’11], can use any cutting plane method and separation oracle for the constraints.
Based on joint work with Niv Buchbinder and Joseph (Seffi) Naor.
To attend this seminar in person, please go the DC 1304. You can also attend virtually on Zoom.