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…
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…