44 citations · 80 across the 32 of their papers we have counts for
41 papers
Efficient Algorithms for Online Subadditive Combinatorial Allocations
Calum MacRury, Rian Neogi, Kanstantsin Pashkovich +4
For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a -competitive online algorithm, improving on…
A simple Path-based LP Relaxation for Directed Steiner Tree
Kanstantsin Pashkovich, Marta Pozzi, Laura Sanità
We study the Directed Steiner Tree (DST) problem in layered graphs through a simple path-based linear programming relaxation. This relaxation achieves an integrality gap of O(l log…
Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
Kanstantsin Pashkovich, Thomas Snow
We study online algorithms for maximum cardinality matchings with edge arrivals in graphs of low degree. Buchbinder, Segev, and Tkach showed that no online algorithm for maximum ca…
Sequential Linear Contracts on Matroids
Kanstantsin Pashkovich, Jacob Skitsko, Yun Xing
In this work, we study sequential contracts under matroid constraints. In the sequential setting, an agent can take actions one by one. After each action, the agent observes the st…
Multidimensional Budget-Feasible Mechanism Design
Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy
In budget-feasible mechanism design, a buyer wishes to procure a set of items of maximum value from self-interested players. We have a valuation function ,…
An -approximate budget feasible mechanism for subadditive valuations
Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy
In budget-feasible mechanism design, there is a set of items , each owned by a distinct seller. The seller of item incurs a private cost for supplying her i…
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…
Linear Contracts for Supermodular Functions Based on Graphs
Kanstantsin Pashkovich, Jacob Skitsko
We study linear contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a linear contract with several agents, each of whom can decide to…
Matroid Bayesian Online Selection
Ian DeHaan, Kanstantsin Pashkovich
We study a class of Bayesian online selection problems with matroid constraints. Consider a vendor who has several items to sell, with the set of sold items being subject to some s…
Single Sample Prophet Inequality for Uniform Matroids of Rank 2
Kanstantsin Pashkovich, Alice Sayutina
We study the prophet inequality when the gambler has an access only to a single sample from each distribution. Rubinstein, Wang and Weinberg showed that an optimal guarantee of 1/2…
Non-Adaptive Prophet Inequalities for Minor-Closed Classes of Matroids
Kanstantsin Pashkovich, Alice Sayutina
We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight -competitive me…
A Two-Step Approach to Optimal Dynamic Pricing in Multi-Demand Combinatorial Markets
Kanstantsin Pashkovich, Xinyue Xie
Online markets are a part of everyday life, and their rules are governed by algorithms. Assuming participants are inherently self-interested, well designed rules can help to increa…
Approximating Stable Matchings with Ties of Bounded Size
Jochen Koenemann, Kanstantsin Pashkovich, Natig Tofigzade
Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete preferences, computing a stable matchin…
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…
Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value
Frits Hof, Walter Kern, Sascha Kurz +2
A simple game is given by a set of players and a partition of~ into a set~ of losing coalitions~ with value that is closed under takin…
Computing the Nucleolus of Weighted Voting Games in Pseudo-polynomial Time
Kanstantsin Pashkovich
We provide an algorithm for computing the nucleolus for an instance of a weighted voting game in pseudo-polynomial time. This resolves an open question posed by Elkind. et.al. 2007…
On the approximability of the stable matching problem with ties of size two
Robert Chiang, Kanstantsin Pashkovich
The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum…
Three-dimensional Stable Matching with Cyclic Preferences
Kanstantsin Pashkovich, Laurent Poirrier
We consider the three-dimensional stable matching problem with cyclic preferences, a problem originally proposed by Knuth. Despite extensive study of the problem by experts from di…
Bounds on the number of 2-level polytopes, cones and configurations
Samuel Fiorini, Marco Macchia, Kanstantsin Pashkovich
We prove an upper bound of the form on the number of affine (resp. linear) equivalence classes of, by increasing order of generality, 2-level d-pol…
On Critical Threshold Value for Simple Games
Kanstantsin Pashkovich
In this note, we show that for every simple game with n players the critical threshold value is at most n/4. This verifies the conjecture of Freixas and Kurz.
On the approximability of the stable marriage problem with one-sided ties
Felix Bauckholt, Kanstantsin Pashkovich, Laura Sanità
The classical stable marriage problem asks for a matching between a set of men and a set of women with no blocking pairs, which are pairs formed by a man and a woman who would both…
Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time
Jochen Koenemann, Kanstantsin Pashkovich, Justin Toth
We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in [Faigle,…
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…
On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Jochen Könemann, Neil Olver, Kanstantsin Pashkovich +3
In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph , edge costs , terminal pairs , and…