research
∙
01/23/2023
Improved Hardness of Approximation for Geometric Bin Packing
The Geometric Bin Packing (GBP) problem is a generalization of Bin Packi...
share
research
∙
11/15/2022
SDPs and Robust Satisfiability of Promise CSP
For a constraint satisfaction problem (CSP), a robust satisfaction algor...
research
∙
04/30/2021
On the Hardness of Scheduling With Non-Uniform Communication Delays
In the scheduling with non-uniform communication delay problem, the inpu...
research
∙
02/23/2021
Conditional Dichotomy of Boolean Ordered Promise CSPs
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of...
research
∙
01/08/2021
Almost Optimal Inapproximability of Multidimensional Packing Problems
Multidimensional packing problems generalize the classical packing probl...
research
∙
08/17/2020
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture
A famous conjecture of Tuza states that the minimum number of edges need...
research
∙
12/28/2019
Minmax Regret for sink location on paths with general capacities
In dynamic flow networks, every vertex starts with items (flow) that nee...
research
∙
11/28/2019
PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching
In the classical Online Metric Matching problem, we are given a metric s...
research
∙
06/11/2018
Minmax-Regret k-Sink Location on a Dynamic Tree Network with Uniform Capacities
A dynamic flow network G with uniform capacity c is a graph in which at ...
research
∙
11/03/2017