TY - JOUR

T1 - Approximation algorithms for min-max cycle cover problems

AU - Xu, Wenzheng

AU - Liang, Weifa

AU - Lin, Xiaola

N1 - Publisher Copyright:
© 1968-2012 IEEE.

PY - 2015/3/1

Y1 - 2015/3/1

N2 - As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph G and an integer k>0 , we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in G with an aim to find k rootless (or rooted) edge-disjoint cycles covering the vertices in V such that the maximum cycle weight among the k cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a (5{ 1\over 3} +\epsilon)-approximation algorithm; for the uncapacitated rooted min-max cycle cover problem, we devise a (6{ 1\over 3} +\epsilon) -approximation algorithm; and for the capacitated rooted min-max cycle cover problem, we propose a (7+\epsilon) -approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems 6+\epsilon, 7+\epsilon , and 13+\epsilon, respectively, where \epsilon is a constant with 0< \epsilon <1. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts.

AB - As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph G and an integer k>0 , we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in G with an aim to find k rootless (or rooted) edge-disjoint cycles covering the vertices in V such that the maximum cycle weight among the k cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a (5{ 1\over 3} +\epsilon)-approximation algorithm; for the uncapacitated rooted min-max cycle cover problem, we devise a (6{ 1\over 3} +\epsilon) -approximation algorithm; and for the capacitated rooted min-max cycle cover problem, we propose a (7+\epsilon) -approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems 6+\epsilon, 7+\epsilon , and 13+\epsilon, respectively, where \epsilon is a constant with 0< \epsilon <1. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts.

KW - Wireless sensor networks

KW - approximation algorithms

KW - combinatorial optimization

KW - data gathering

KW - min-max cycle cover

KW - mobile sinks

KW - tree decomposition

KW - vehicle routing problem

UR - http://www.scopus.com/inward/record.url?scp=84923103056&partnerID=8YFLogxK

U2 - 10.1109/TC.2013.2295609

DO - 10.1109/TC.2013.2295609

M3 - Article

SN - 0018-9340

VL - 64

SP - 600

EP - 613

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 3

M1 - 6690147

ER -