44 citations · 80 across the 32 of their papers we have counts for
8 papers · 1 filter
Normalizations of factorizations over convex cones and their effects on extension complexity
Adam Brown, Kanstantsin Pashkovich, Levent Tunçel
Factorizations over cones and their duals play central roles for many areas of mathematics and computer science. One of the reasons behind this is the ability to find a representat…
The Aggregation Closure is Polyhedral for Packing and Covering Integer Programs
Kanstantsin Pashkovich, Laurent Poirrier, Haripriya Pulyassary
Recently, Bodur, Del Pia, Dey, Molinaro and Pokutta introduced the concept of aggregation cuts for packing and covering integer programs. The aggregation closure is the intersectio…
On the Circuit Diameter of some Combinatorial Polytopes
Sean Kafer, Kanstantsin Pashkovich, Laura Sanità
The combinatorial diameter of a polytope is the maximum value of a shortest path between two vertices of , where the path uses the edges of only. In contrast to the comb…
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…
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…
Small Extended Formulations for Cyclic Polytopes
Yuri Bogomolov, Samuel Fiorini, Aleksandr Maksimenko +1
We provide an extended formulation of size O(log n)^{\lfloor d/2 \rfloor} for the cyclic polytope with dimension d and n vertices (i,i^2,\ldots,i^d), i in [n]. First, we find an ex…
Uncapacitated Flow-based Extended Formulations
Samuel Fiorini, Kanstantsin Pashkovich
An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extende…
Which Nonnegative Matrices Are Slack Matrices?
João Gouveia, Roland Grappe, Volker Kaibel +3
In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack ma…