Algorithms for the metric ring star problem with fixed edge-cost ratio

摘要

Abstract We address the metric ring star problem with fixed edge-cost ratio, abbreviated as RSP. Given a complete graph G=(V,E)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$G=(V,E)$$end{document} with a specified depot node d∈Vdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$din V$$end{document}, a nonnegative cost function c∈R+Edocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$cin mathbb {R}_+^E$$end{document} on E which satisfies the triangle inequality, and an edge-cost ratio M≥1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$Mge 1$$end{document}, the RSP is to locate a ring R=(V′,E′)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$R=(V',E')$$end{document} in G, a simple cycle through d or d itself, aiming to minimize the sum of two costs: the cost for constructing ring R, i.e., M·∑e∈E′c(e)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$Mcdot sum _{ein E'}c(e)$$end{document}, and the cost for attaching nodes in VV′documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$V{setminus } V'$$end{document} to their closest ring nodes (in R), i.e., ∑u∈VV′minv∈V′c(uv)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$sum _{uin V{setminus } V'}min _{vin V'}c(uv)$$end{document}. We show that the singleton ring d is an optimal solution of the RSP when M≥(|V|-1)/2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$Mge (|V|-1)/2$$end{document}. This particularly implies a |V|-1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$sqrt{|V|-1}$$end{document}-approximation algorithm for the RSP with any M≥1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$Mge 1$$end{document}. We present randomized 3-approximation algorithm and deterministic 5.06-approximation algorithm for the RSP, by adapting algorithms for the tour-connected facility location problem (tour-CFLP) and single-source rent-or-buy problem due to Eisenbrand et al. and Williamson and van Zuylen, respectively. Building on the PTAS of Eisenbrand et al. for the tour-CFLP, we give a PTAS for the RSP with |V|/M=O(1)