research
∙
08/29/2023
Approximate Monotone Local Search for Weighted Problems
In a recent work, Esmer et al. describe a simple method - Approximate Mo...
share
research
∙
08/24/2023
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
We study the Uniform Cardinality Constrained Multiple Knapsack problem (...
research
∙
07/15/2023
Tight Lower Bounds for Weighted Matroid Problems
In this paper we derive tight lower bounds resolving the hardness status...
research
∙
07/09/2023
Budgeted Matroid Maximization: a Parameterized Viewpoint
We study budgeted variants of well known maximization problems with mult...
research
∙
07/05/2023
Improved Approximation for Two-dimensional Vector Multiple Knapsack
We study the uniform 2-dimensional vector multiple knapsack (2VMK) probl...
research
∙
06/27/2023
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
The goal of this paper is to understand how exponential-time approximati...
research
∙
04/27/2023
An FPTAS for Budgeted Laminar Matroid Independent Set
We study the budgeted laminar matroid independent set problem. The input...
research
∙
02/11/2023
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection
We study the budgeted versions of the well known matching and matroid in...
research
∙
12/02/2022
Bin Packing with Partition Matroid can be Approximated within o(OPT) Bins
We consider the Bin Packing problem with a partition matroid constraint....
research
∙
09/10/2022
An EPTAS for Budgeted Matroid Independent Set
We consider the budgeted matroid independent set problem. The input is a...
research
∙
09/04/2022
Computing Generalized Convolutions Faster Than Brute Force
In this paper, we consider a general notion of convolution. Let D be a f...
research
∙
06/27/2022
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
We generalize the monotone local search approach of Fomin, Gaspers, Loks...
research
∙
05/25/2022
An Asymptotic (4/3+ε)-Approximation for the 2-Dimensional Vector Bin Packing Problem
We study the 2-Dimensional Vector Bin Packing Problem (2VBP), a generali...
research
∙
02/25/2021
A Refined Analysis of Submodular Greedy
Many algorithms for maximizing a monotone submodular function subject to...
research
∙
07/20/2020
Tight Approximations for Modular and Submodular Optimization with d-Resource Multiple Knapsack Constraints
A multiple knapsack constraint over a set of items is defined by a set o...
research
∙
04/25/2020
A (1-e^-1-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
We study the problem of maximizing a monotone submodular function subjec...
research
∙
11/06/2019
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
In this paper we introduce randomized branching as a tool for parameteri...
research
∙
07/03/2019