21 citations · 33 across the 8 of their papers we have counts for
8 papers · 1 filter
A -approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds
Moritz Buchem, Katja Ettmayr, Hugo Kooki Kasuya Rosado +1
For a given set of points in a metric space and an integer , we seek to partition the given points into clusters. For each computed cluster, one typically defines one point…
Simpler constant factor approximation algorithms for weighted flow time -- now for any -norm
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time…
Optimal Fully Dynamic -Center Clustering for Adaptive and Oblivious Adversaries
MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger +4
In fully dynamic clustering problems, a clustering of a given data set in a metric space must be maintained while it is modified through insertions and deletions of individual poin…
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
An important objective in scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs where each job is characterized by a release time, a proce…
On fully dynamic constant-factor approximation algorithms for clustering problems
Hendrik Fichtenberger, Monika Henzinger, Andreas Wiese
Clustering is an important task with applications in many fields of computer science. We study the fully dynamic setting in which we want to maintain good clusters efficiently when…
Approximation and parameterized algorithms for geometric independent set with shrinking
Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlappin…