1 citations · 1 across the 16 of their papers we have counts for
31 papers
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…