44 citations · 80 across the 32 of their papers we have counts for
4 papers · 1 filter
Every rational polyhedron has finite split rank: new proof
Kanstantsin Pashkovich
Split rank of a rational polyhedron is finite. The well known proof of this is based on the fact that split closure is stronger than the Chvátal closure, and the Chvátal rank of a…
An Elementary Integrality Proof of Rothblum's Stable Matching Formulation
Jochen Könemann, Kanstantsin Pashkovich, Justin Toth
In this paper we provide a short new proof for the integrality of Rothblum's linear description of the convex hull of incidence vectors of stable matchings in bipartite graphs. In…
Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich +1
In a standard -connectivity network design problem, we are given an undirected graph , a cut-requirement function , and non-negative cos…
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs
Samuel Fiorini, Tony Huynh, Gwenaël Joret +1
We give an -size extended formulation for the spanning tree polytope of an -vertex graph embedded on a surface of genus , improving on t…