3 citations · 7 across the 8 of their papers we have counts for
4 papers · 1 filter
Fooling Sets and the Spanning Tree Polytope
Kaveh Khoshkhah, Dirk Oliver Theis
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum S…
Nondeterministic Communication Complexity of Random Boolean Functions
Mozhgan Pourmoradnasseri, Dirk Oliver Theis
We study nondeterministic communication complexity and related concepts (fooling sets, fractional covering number) of random functions where each va…
The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
Abdullah Makkeh, Mozhgan Pourmoradnasseri, Dirk Oliver Theis
Graphs (1-skeletons) of Traveling-Salesman-related polytopes have attracted a lot of attention. Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Prob…
On the Graph of the Pedigree Polytope
Abdullah Makkeh, Mozhgan Pourmoradnasseri, Dirk Oliver Theis
Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes whose graphs (1-skeletons) contain the TSP polytope graphs as spanning subgraphs.…