### Abstract

A complete weighted graph G = (V, E, w) is called Δ_{β} -metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., w(u, v) ≤ β · (w(u, x) + w(x, v)) for all vertices u, v, x ∈ V. Given a Δ_{β} -metric graph G = (V, E, w) and an integer p, the Δ_{β} -pHub Center Problem (Δ_{β} -pHCP) is to find a spanning subgraph H^{∗} of G such that (i) vertices (hubs) in C^{∗} ⊂V form a clique of size p in H^{∗} ; (ii) vertices (non-hubs) in V \C^{∗} form an independent set in H^{∗} ; (iii) each non-hub v ∈ V \C^{∗} is adjacent to exactly one hub in C^{∗} ; and (iv) the diameter D(H^{∗} ) is minimized. For β = 1, Δ_{β} -pHCP is NP-hard. (Chen et al., CMCT 2016) proved that for any ε > 0, it is NP-hard to approximate the Δ_{β} -pHCP to within a ratio^{4}_{3} − ε for β = 1. In the same paper, a^{5}_{3} -approximation algorithm was given for Δ_{β}-pHCP for β = 1. In this paper, we study Δ_{β} -pHCP for all β ≥^{1}_{2}. We show that for any ε > 0, to approximate the Δ_{β} -pHCP to a ratio g(β) − ε is NP-hard and we give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. If β ≤^{3−√}_{2}^{3}, we have r(β) = g(β) = 1, i.e., Δ_{β} -pHCP is polynomial time solvable. If^{3−√}_{2}^{3} < β ≤^{2}_{3}, we have r(β) = g(β) =^{3β−2β2}_{3(1−β)}. For^{2}_{3} ≤ β ≤^{5+√}_{10}^{5}, r(β) = g(β) = β + β^{2}. Moreover, for β ≥ 1, we have g(β) = β ·^{4β−1}_{3β−1} and r(β) = 2β, the approximability of the problem (i.e., upper and lower bound) is linear in β.

Original language | English |
---|---|

Title of host publication | Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings |

Editors | Yixin Cao, Jianer Chen |

Publisher | Springer Verlag |

Pages | 112-123 |

Number of pages | 12 |

ISBN (Print) | 9783319623887 |

DOIs | |

Publication status | Published - 2017 Jan 1 |

Event | 23rd International Conference on Computing and Combinatorics, COCOON 2017 - Hong Kong, China Duration: 2017 Aug 3 → 2017 Aug 5 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10392 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 23rd International Conference on Computing and Combinatorics, COCOON 2017 |
---|---|

Country | China |

City | Hong Kong |

Period | 17-08-03 → 17-08-05 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'The approximability of the p-hub center problem with parameterized triangle inequality'. Together they form a unique fingerprint.

## Cite this

*Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings*(pp. 112-123). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10392 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-62389-4_10