research
∙
08/11/2023
Simpler constant factor approximation algorithms for weighted flow time – now for any p-norm
A prominent problem in scheduling theory is the weighted flow time probl...
share
research
∙
03/21/2023
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
In fully dynamic clustering problems, a clustering of a given data set i...
research
∙
03/16/2023
Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set
Set cover and hitting set are fundamental problems in combinatorial opti...
research
∙
08/05/2022
A PTAS for Minimizing Weighted Flow Time on a Single Machine
An important objective in scheduling literature is to minimize the sum o...
research
∙
02/12/2022
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
In the Strip Packing problem (SP), we are given a vertical half-strip [0...
research
∙
02/07/2022
Approximation Algorithms for ROUND-UFP and ROUND-SAP
We study ROUND-UFP and ROUND-SAP, two generalizations of the classical B...
research
∙
12/14/2021
On fully dynamic constant-factor approximation algorithms for clustering problems
Clustering is an important task with applications in many fields of comp...
research
∙
11/09/2021
A PTAS for the horizontal rectangle stabbing problem
We study rectangle stabbing problems in which we are given n axis-aligne...
research
∙
06/01/2021
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
We study the Maximum Independent Set of Rectangles (MISR) problem, where...
research
∙
03/18/2021
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsa...
research
∙
03/17/2021
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem
In two-dimensional geometric knapsack problem, we are given a set of n a...
research
∙
11/11/2020
A (2+ε)-approximation algorithm for preemptive weighted flow time on a single machine
Weighted flow time is a fundamental and very well-studied objective func...
research
∙
07/31/2020
On the Two-Dimensional Knapsack Problem for Convex Polygons
We study the two-dimensional geometric knapsack problem for convex polyg...
research
∙
07/18/2020
Additive Approximation Schemes for Load Balancing Problems
In this paper we introduce the concept of additive approximation schemes...
research
∙
07/16/2020
Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
Knapsack problems are among the most fundamental problems in optimizatio...
research
∙
03/05/2020
Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles
Independent set is a fundamental problem in combinatorial optimization. ...
research
∙
02/24/2020
Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity
Graph coloring is a fundamental problem in computer science. We study th...
research
∙
11/25/2019
Breaking the Barrier of 2 for the Storage Allocation Problem
Packing problems are an important class of optimization problems. The pr...
research
∙
06/26/2019
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
The area of parameterized approximation seeks to combine approximation a...
research
∙
02/27/2019
On the extension complexity of scheduling
Linear programming is a powerful method in combinatorial optimization wi...
research
∙
07/19/2018
Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
We consider two optimization problems in planar graphs. In Maximum Weigh...
research
∙
11/21/2017
Approximating Geometric Knapsack via L-packings
We study the two-dimensional geometric knapsack problem (2DK) in which w...
research
∙
12/12/2012