Abstract
This report explores three concepts: the k-center problem, its variants, and asymmetry.
We demonstrate an O(log* n)-approximation algorithm for the asymmetric weighted k-center problem. For the p-neighbor k-center problem we give an O(log* k)-bicriteria algorithm using 2k centers, for small p.
Turning to approximability we show that the priority k-center problem, the k-supplier problem, and the k-center problem with outliers and forbidden centers are inapproximable. These versions all admit constant factor algorithms in the symmetric case.
We demonstrate an O(log* n)-approximation algorithm for the asymmetric weighted k-center problem. For the p-neighbor k-center problem we give an O(log* k)-bicriteria algorithm using 2k centers, for small p.
Turning to approximability we show that the priority k-center problem, the k-supplier problem, and the k-center problem with outliers and forbidden centers are inapproximable. These versions all admit constant factor algorithms in the symmetric case.
Originalsprog | Engelsk |
---|
Udgivelsessted | Copenhagen |
---|---|
Forlag | IT-Universitetet i København |
Udgave | TR-2003-24 |
Antal sider | 14 |
ISBN (Elektronisk) | 87-7949-033-6 |
Status | Udgivet - 2003 |
Udgivet eksternt | Ja |
Navn | IT University Technical Report Series |
---|---|
Nummer | TR-2003-24 |
ISSN | 1600-6100 |