Campus Event Calendar
Event Entry
What and Who
A faster PTAS for the k-disc cover problem in Euclidean space
Rouven Naujoks
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 22 September 2006
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
Suppose you are given n points in d-dimensional Euclidean space. The k-disc cover problem is to find k balls covering these n points while minimizing the sum of the balls' volumes. We show that there is a polynomial time approximation scheme for this problem that runs in time linear in n and polynomial in k. This improves upon the previously best known running time which is a (large) polynomial in n.
Contact
Rouven Naujoks
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
computational geometry
Rouven Naujoks, 09/15/2006 12:24
Rouven Naujoks, 09/15/2006 12:24 -- Created document.
Rouven Naujoks, 09/15/2006 12:24 -- Created document.