Skip navigation
Skip navigation

Approximation Algorithms for Min-Max Cycle Cover Problems

Xu, Wenzheng; Liang, Weifa; Lin, Xiaola

Description

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...[Show more]

dc.contributor.authorXu, Wenzheng
dc.contributor.authorLiang, Weifa
dc.contributor.authorLin, Xiaola
dc.date.accessioned2015-03-11T22:34:12Z
dc.date.available2015-03-11T22:34:12Z
dc.identifier.issn0018-9340
dc.identifier.urihttp://hdl.handle.net/1885/12872
dc.description.abstractAs 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/3+ ε)-approximation algorithm; for the uncapacitated rooted min-max cycle cover problem, we devise a (6 1/3 + ε)-approximation algorithm; and for the capacitated rooted min-max cycle cover problem, we propose a (7+ε)-approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems 6+ε , 7+ε , and 13+ε , respectively, where ε is a constant with 0 < ε < 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.
dc.publisherIEEE
dc.rights© 2013 IEEE
dc.sourceIEEE Transactions on Computers
dc.subjectWireless sensor networks
dc.subjectdata gathering
dc.subjectmobile sinks
dc.subjectvehicle routing problem
dc.subjectmin-max cycle cover
dc.subjecttree decomposition
dc.subjectapproximation algorithms
dc.subjectcombinatorial optimization
dc.titleApproximation Algorithms for Min-Max Cycle Cover Problems
dc.typeJournal article
local.identifier.citationvolume64
dcterms.dateAccepted2013-12-04
dc.date.issued2015-02-11
local.identifier.absfor080401 - Coding and Information Theory
local.identifier.absfor100510 - Wireless Communications
local.identifier.absfor080201 - Analysis of Algorithms and Complexity
local.identifier.ariespublicationu4334215xPUB1351
local.publisher.urlhttp://www.ieee.org/index.html
local.type.statusPublished version
local.contributor.affiliationXu, W., Research School of Computer Science, The Australian National University
local.contributor.affiliationLiang, W., Research School of Computer Science, The Australian National University
local.bibliographicCitation.issue3
local.bibliographicCitation.startpage600
local.bibliographicCitation.lastpage613
local.identifier.doi10.1109/TC.2013.2295609
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
dc.date.updated2015-12-10T10:37:10Z
local.identifier.scopusID2-s2.0-84923103056
CollectionsANU Research Publications

Download

There are no files associated with this item.


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator