A simple greedy approximation algorithm for the minimum connected k-center problem

DOI10.1007/S10878-015-9831-8MaRDI QIDQ281773zbMATH OpenOpenAlexFDO

Authors Dongyue Liang, Liquan Mei, James Willson, Wei Wang

Publication date 11 May 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-015-9831-8

zbMATH Keywords

approximation algorithmgreedy algorithm\(k\)-center

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Approximability results for the converse connected \(p\)-centre problem
• The connected \(p\)-center problem on cactus graphs
• A Best Possible Heuristic for the k-Center Problem
• Fault tolerant \(K\)-center problems
• scientific article; zbMATH DE number 1163715

Cites work

• scientific article; zbMATH DE number 1757943 (Why is no real title available?)
• A Best Possible Heuristic for the k-Center Problem
• A simple heuristic for the p-centre problem
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• Asymmetric k -center is log ^* n -hard to approximate
• Fault tolerant \(K\)-center problems
• Graph theory with applications
• The Capacitated K-Center Problem
• The design of approximation algorithms

Cited in

(2)

• Approximability results for the converse connected \(p\)-centre problem
• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem

This page was built for publication: A simple greedy approximation algorithm for the minimum connected \(k\)-center problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281773)