44 citations · 80 across the 32 of their papers we have counts for
4 papers · 1 filter
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…