research
∙
08/24/2023
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
We study the Uniform Cardinality Constrained Multiple Knapsack problem (...
share
research
∙
07/17/2023
Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs
We consider the classic budgeted maximum weight independent set (BMWIS) ...
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
∙
04/27/2023
An FPTAS for Budgeted Laminar Matroid Independent Set
We study the budgeted laminar matroid independent set problem. The input...
research
∙
02/21/2023
Approximating Bin Packing with Conflict Graphs via Maximization Techniques
We give a comprehensive study of bin packing with conflicts (BPC). The i...
research
∙
02/17/2023
Finding Possible and Necessary Winners in Spatial Voting with Partial Information
We consider spatial voting where candidates are located in the Euclidean...
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
∙
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
∙
11/09/2020
An APTAS for Bin Packing with Clique-graph Conflicts
We study the following variant of the classic bin packing problem. The i...
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
Generalized Assignment via Submodular Optimization with Reserved Capacity
We study a variant of the generalized assignment problem ( GAP) with gro...
research
∙
11/18/2018