|
|
|
|
a simple greedy approximation algorithm for the unit disk cover problem
|
|
|
|
|
|
|
|
نویسنده
|
imanparast mahdi ,hashemi naser
|
|
منبع
|
aut journal of mathematics and computing - 2020 - دوره : 1 - شماره : 1 - صفحه:47 -55
|
|
چکیده
|
Given a set p of n points in the plane, the unit disk cover problem, which is known as an np-hard problem, seeks to find the minimum number of unit disks that can cover all points of p. we present a new 4-approximation algorithm with running time o(n log n) for this problem. our proposed algorithm uses a simple approach and is easy to understand and implement.
|
|
کلیدواژه
|
computational geometry ,approximation algorithms ,unit disk cover problem ,facility location
|
|
آدرس
|
amirkabir university of technology, department of mathematics and computer science, iran, amirkabir university of technology, department of mathematics and computer science, iran
|
|
پست الکترونیکی
|
nhashemi@aut.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|