5 citations · 17 across the 10 of their papers we have counts for
14 papers · 1 filter
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…
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
Arindam Khan, Aditya Lonkar, Arnab Maiti +2
In the Strip Packing problem (SP), we are given a vertical half-strip and a set of axis-aligned rectangles of width at most . The goal is to find a n…
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem
Arindam Khan, Arnab Maiti, Amatya Sharma +1
In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, inte…
A -approximation algorithm for preemptive weighted flow time on a single machine
Lars Rohwedder, Andreas Wiese
Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input cons…
On the Two-Dimensional Knapsack Problem for Convex Polygons
Arturo Merino, Andreas Wiese
We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitabl…
Additive Approximation Schemes for Load Balancing Problems
Moritz Buchem, Lars Rohwedder, Tjark Vredeveld +1
In this paper we introduce the concept of additive approximation schemes and apply it to load balancing problems. Additive approximation schemes aim to find a solution with an abso…