Hardness and Approximation for the Star β -Hub Routing Cost Problem in Δβ -Metric Graphs

Meng Shiou Tsai, Sun Yuan Hsieh, Ling Ju Hung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Minimizing transportation costs through the design of a hub-and-spoke network is a crucial concern in hub location problems (HLP). Within the realm of HLP, the Δβ -Star p -Hub Routing Cost Problem (Δβ -SpHRP) represents an open problem stemming from the Star p -Hub Routing Cost Problem (SpHRP) discussed in a publication by [Yeh et al., Theoretical Computer Science, 2022]. The Δβ -SpHRP deals with a specific vertex c, a positive integer p, and a Δβ -metric graph denoted as G, which is an undirected, complete, and weighted graph adhering to the β -triangle inequality. The objective is to identify a spanning tree T that satisfies the following conditions: it is rooted at c, contains exactly p hubs adjacent to c, and assigns each remaining vertex to a hub while minimizing the routing cost of T. This paper expands the input instances from metric graphs to Δβ -metric graphs. Our research demonstrates that SpHRP is NP-hard for any β>12, indicating that SpHRP remains NP-hard for various subclasses of metric graphs. For approximation algorithms, we introduce two approaches that improve upon previous results, particularly when β is close to 12.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
EditorsWeili Wu, Guangmo Tong
PublisherSpringer Science and Business Media Deutschland GmbH
Pages97-111
Number of pages15
ISBN (Print)9783031491894
DOIs
Publication statusPublished - 2024
Event29th International Computing and Combinatorics Conference, COCOON 2023 - Hawaii, United States
Duration: 2023 Dec 152023 Dec 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14422 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Computing and Combinatorics Conference, COCOON 2023
Country/TerritoryUnited States
CityHawaii
Period23-12-1523-12-17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Hardness and Approximation for the Star β -Hub Routing Cost Problem in Δβ -Metric Graphs'. Together they form a unique fingerprint.

Cite this