A mixed breadth-depth first strategy for the branch and bound tree of Euclidean k-center problems

Hatem Fayed () and Amir Atiya ()

Computational Optimization and Applications, 2013, vol. 54, issue 3, 675-703

Abstract: The k-center problem arises in many applications such as facility location and data clustering. Typically, it is solved using a branch and bound tree traversed using the depth first strategy. The reason is its linear space requirement compared to the exponential space requirement of the breadth first strategy. Although the depth first strategy gains useful information fast by reaching some leaves early and therefore assists in pruning the tree, it may lead to exploring too many subtrees before reaching the optimal solution, resulting in a large search cost. To speed up the arrival to the optimal solution, a mixed breadth-depth traversing strategy is proposed. The main idea is to cycle through the nodes of the same level and recursively explore along their first promising paths until reaching their leaf nodes (solutions). Thus many solutions with diverse structures are obtained and a good upper bound of the optimal solution can be achieved by selecting the minimum among them. In addition, we employ inexpensive lower and upper bounds of the enclosing balls, and this often relieves us from calling the computationally expensive exact minimum enclosing ball algorithm. Experimental work shows that the proposed strategy is significantly faster than the naked branch and bound approach, especially as the number of centers and/or the required accuracy increases. Copyright Springer Science+Business Media, LLC 2013

Keywords: k-Center; Minimum enclosing ball; Branch and bound; Breadth first; Depth first (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-012-9503-x (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:54:y:2013:i:3:p:675-703

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-012-9503-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().