research
∙
06/07/2023
Matroid-Constrained Vertex Cover
In this paper, we introduce the problem of Matroid-Constrained Vertex Co...
share
research
∙
07/08/2022
Maximum Weight b-Matchings in Random-Order Streams
We consider the maximum weight b-matching problem in the random-order se...
research
∙
05/30/2022
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is t...
research
∙
01/27/2022
Vizing's and Shannon's Theorems for defective edge colouring
We call a multigraph (k,d)-edge colourable if its edge set can be partit...
research
∙
07/27/2021
Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
We consider the problem of maximizing a non-negative submodular function...
research
∙
02/18/2021
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
We give improved multi-pass streaming algorithms for the problem of maxi...
research
∙
11/12/2020
FPT-Algorithms for the l-Matchoid Problem with Linear and Submodular Objectives
We design a fixed-parameter deterministic algorithm for computing a maxi...
research
∙
05/01/2020
Approximating maximum integral multiflows on bounded genus graphs
We devise the first constant-factor approximation algorithm for finding ...
research
∙
02/13/2020
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
Maximizing a monotone submodular function under various constraints is a...
research
∙
01/06/2020
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
We devise a constant-factor approximation algorithm for the maximization...
research
∙
02/17/2018
