activity
20132026
most citedA Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

31 citations · 56 across the 21 of their papers we have counts for

collaborators
Showing 2023Show all

2 papers · 1 filter

cs.DM2023

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

Jamico Schade, Makrand Sinha, Stefan Weltge

Standard mixed-integer programming formulations for the stable set problem on -node graphs require integer variables. We prove that this is almost optimal: We give a family…

cs.DS2023

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set

Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini +2

We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph with non-negative vertex costs. The goal is to find a mini…