A PTAS for a disc covering problem using width-bounded separators

DOI10.1007/s10878-006-7132-yzbMath1130.90050MaRDI QIDQ2498985

Binhai Zhu, Zhixiang Chen, Bin Fu, Yong Tang

Publication date: 14 August 2006

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

Full work available at URL: https://doi.org/10.1007/s10878-006-7132-y

zbMATH Keywords

approximation algorithms; randomized algorithms; polynomial time approximation scheme; disc covering; width-bounded separator

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms