Discrete Mathematics and Optimization Seminar

---

DAVID HARTVIGSEN
University of Notre Dame
Monday March 12th at 4.30pm
Burnside 1205



Title. A Greedy Algorithm for Multi-jump Systems

Abstract. Greedy algorithms are known to find optimal solutions for a variety of
structures in combinatorial optimization. In this talk we introduce a new such
structure, called a multi-jump system. Multi-jump systems are a slight generalization of
jump systems (introduced by Bouchet and Cunningham), which, in turn, generalize integral
bisubmodular polyhedra, integral polymatroids, delta-matroids, matroids, and other
structures. We show that multi-jump systems provide a new, systematic, and simple way to
characterize these other structures. Our main result is that a straightforward greedy
algorithm always finds an optimal solution over multi-jump systems. For many of the
special cases of multi-jump systems, this algorithm appears to be new.