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

DOI10.1007/S10878-015-9831-8zbMATH Open1347.90073OpenAlexW2028082337MaRDI QIDQ281773FDOQ281773

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

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

zbMATH Keywords

approximation algorithmgreedy algorithm\(k\)-center

Mathematics Subject Classification ID

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

Cites Work

• The design of approximation algorithms
• Graph theory with applications
• A Best Possible Heuristic for the k-Center Problem
• The Capacitated K-Center Problem
• Fault tolerant \(K\)-center problems
• Asymmetric k -center is log ^* n -hard to approximate
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• Title not available (Why is that?)
• A simple heuristic for the p-centre problem

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)