Kanstantsin Pashkovich

activity

20092026

most citedSymmetry Matters for Sizes of Extended Formulations

44 citations · 80 across the 32 of their papers we have counts for

collaborators

Showing 2016 · math.COShow all

2 papers · 2 filters

math.CO2016★ 1 cited

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…

math.CO2016★ 11 cited

Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs

Samuel Fiorini, Tony Huynh, Gwenaël Joret +1

We give an $O (g^{1/2} n^{3/2} + g^{3/2} n^{1/2})$ -size extended formulation for the spanning tree polytope of an $n$ -vertex graph embedded on a surface of genus $g$ , improving on t…