Two personification strategies for solving circles packing problem

Authors
Citation
Wq. Huang et Rc. Xu, Two personification strategies for solving circles packing problem, SCI CHINA E, 42(6), 1999, pp. 595-602
Citations number
10
Categorie Soggetti
Engineering Management /General
Journal title
SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES
ISSN journal
20950624 → ACNP
Volume
42
Issue
6
Year of publication
1999
Pages
595 - 602
Database
ISI
SICI code
2095-0624(199912)42:6<595:TPSFSC>2.0.ZU;2-A
Abstract
Two personification strategies are presented, which yield a highly efficien t and practical algorithm for solving one of the NP hard problems-circles p acking problem on the basis of the quasi-physical algorithm. A very clever polynomial time complexity degree approximate algorithm for solving this pr oblem has been reported by Dorit S. Hochbaum and Wolfgang Maass in J. ACM. Their algorithm is extremely thorough-going and of great theoretical signif icance. But, just as they pointed out, their algorithm is feasible only in conception and even for examples frequently encountered in everyday life an d of small scale, it is the case more often than not that up to a million y ears would be needed to perform calculations with this algorithm. It is sug gested toward the end of their paper that a heuristic algorithm of higher p ractical effectiveness should be sought out. A direct response to their sug gestion is intented to provide.