Treffer: A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
Title:
A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
Authors:
Contributors:
The Pennsylvania State University CiteSeerX Archives
Publication Year:
2006
Collection:
CiteSeerX
Document Type:
Fachzeitschrift
text
File Description:
application/pdf
Language:
English
Availability:
Rights:
Metadata may be used without restrictions as long as the oai identifier remains attached to it.
Accession Number:
edsbas.54706DC9
Database:
BASE
Weitere Informationen
We consider the following packing problem. Let α be a fixed real in (0, 1]. We are given a bounding rectangle ρ and a set R of n possibly intersecting unit disks whose centers lie in ρ. The task is to pack a set B of m disjoint disks of radius α into ρ such that no disk in B intersects a disk in R, where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for α = 2/3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for α = 2/3 and have shown that the problem cannot be solved in polynomial time for any α> 13/14 unless P = NP.