Campus Event Calendar

Event Entry

What and Who

Traversing combinatorial polytopes via optimization.

Arturo Merino
Saarland University
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 6 June 2023
30 Minutes
E1 4


We present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes.

Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X ⊆ {0,1}^n. The algorithm uses as a black box any algorithm that solves the classical linear optimization problem, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only a polylogarithmic factor larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings.
As a concrete example application of our framework, we obtain an O(T⋅log n) delay algorithm for the vertex enumeration problem on 0/1 polytopes, where T is the time needed to solve a linear program and n is the dimension of the polytope. This improves upon the 25-year-old O(T⋅n) delay algorithm due to Bussieck and Lübbecke.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 06/05/2023 18:32
Roohani Sharma, 05/23/2023 12:32 -- Created document.