1 citations · 1 across the 5 of their papers we have counts for
11 papers
Metric Planarity Testing is Hard
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…
Query-efficient winner prediction in district-based elections
Koustav De, Debajyoti Kar, Swagato Sanyal
In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality rule (i.e.…
On Linear-Size Guillotine-Separable Subsets of Fat Convex Objects, Disks, and Squares
Mark de Berg, Debajyoti Kar, Arindam Khan +1
Let be a family of pairwise disjoint objects in the plane. We say that a subset is \emph{separable} if it admits a sequence of gu…
Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
Debajyoti Kar, Arindam Khan, Andreas Wiese
We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The object…
Improved Approximation Algorithms for Three-Dimensional Knapsack
Klaus Jansen, Debajyoti Kar, Arindam Khan +2
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective…
Improved Approximation Algorithms for Three-Dimensional Bin Packing
Debajyoti Kar, Arindam Khan, Malin Rau
We study two fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), and 3D Minimum Volume Bounding Box (3D-MVBB), where given a set of 3…
Random-Order Online Independent Set of Intervals and Hyperrectangles
Mohit Garg, Debajyoti Kar, Arindam Khan
In the Maximum Independent Set of Hyperrectangles problem, we are given a set of (possibly overlapping) -dimensional axis-aligned hyperrectangles, and the goal is to find a…
Parameterized Guarantees for Almost Envy-Free Allocations
Siddharth Barman, Debajyoti Kar, Shraddha Pathak
We study fair allocation of indivisible goods among agents with additive valuations. We obtain novel approximation guarantees for three of the strongest fairness notions in discret…
Sampling-Based Winner Prediction in District-Based Elections
Palash Dey, Debajyoti Kar, Swagato Sanyal
In a district-based election, we apply a voting rule to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the elec…
Approximation Algorithms for ROUND-UFP and ROUND-SAP
Debajyoti Kar, Arindam Khan, Andreas Wiese
We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN PACKING problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocati…
Feature-based Individual Fairness in k-Clustering
Debajyoti Kar, Mert Kosan, Debmalya Mandal +4
Ensuring fairness in machine learning algorithms is a challenging and essential task. We consider the problem of clustering a set of points while satisfying fairness constraints. W…