The minimum bounded diameter spanning forest problem is log-approximable
Alfandari, Laurent (2001), The minimum bounded diameter spanning forest problem is log-approximable, Foundations of Computing and Decision Sciences, 26, 1, p. 123-132
TypeArticle accepté pour publication ou publié
Journal nameFoundations of Computing and Decision Sciences
MetadataShow full item record
Abstract (EN)A number of location problems in networks with nodal demand consist in finding a minimum-cost partition of nodes. In the minimum bounded-diameter spanning forest problem, the network is partitioned into a minimum number of trees such that the weighted diameter of every tree in the partition does not exceed a given bound B. This problem models applications such as dividing a sales area into a minimum number of regions so that a salesman should not drive more than B kilometers or hours for visiting any two customers in a region. We show that it is equivalent to finding a least set of points in the network such that the distance from the farthest demand node to the set is bounded, which is the converse version of the well-known absolute k-center problem. Finally, we adapt the greedy Set Covering heuristic to our problem using an approach called "master-slave", in order to prove approximability within log-factor.
Subjects / KeywordsPartition; approximability; greedy Set Covering heuristic; minimum bounded-diameter spanning forest problem
Showing items related by title and author.