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.
| Original language | English |
|---|
| Place of Publication | Copenhagen |
|---|---|
| Publisher | IT-Universitetet i København |
| Edition | TR-2003-24 |
| Number of pages | 14 |
| ISBN (Electronic) | 87-7949-033-6 |
| Publication status | Published - 2003 |
| Externally published | Yes |
| Series | IT University Technical Report Series |
|---|---|
| Number | TR-2003-24 |
| ISSN | 1600-6100 |
Keywords
- k-center problem
- asymmetric weighted k-center
- p-neighbor k-center problem
- approximation algorithms
- inapproximability