Tobias Uhlig
ABSTRACT
The k-center problem is a fundamental problem we often face when considering complex service systems. Typical challenges include the placement of warehouses in logistics or positioning of servers for content delivery networks. We previously have proposed Dragoon as an effective algorithm to approach the k-center problem. This paper evaluates Dragoon with a focus on potential worst case behavior in comparison to other techniques. We use an evolutionary algorithm to generate instances of the k-center problem that are especially challenging for Dragoon. Ultimately, our experiments confirm the previous good results of Dragoon, however, we also can reliably find scenarios where it is clearly outperformed by other approaches.
- Gonzalez, T. F. 1985. "Clustering to Minimize the Maximum Intercluster Distance". Theoretical Computer Science 38:293 -- 306.Google Scholar
Cross Ref
- Hillmann, P., L. Stiemert, G. D. Rodosek, and O. Rose. 2015a, Dec. "Dragoon: Advanced Modelling of IP Geolocation by Use of Latency Measurements". In 2015 10th International Conference for Internet Technology and Secured Transactions (ICITST), 438--445.Google Scholar
- Hillmann, P., L. Stiemert, G. D. Rodosek, and O. Rose. 2015b, Nov. "Modelling of IP Geolocation by Use of Latency Measurements". In Network and Service Management (CNSM), 2015 11th International Conference on, 173--177. Google ScholarDigital Library
- Hillmann, P., T. Uhlig, G. D. Rodosek, and O. Rose. 2015, Nov. "A Novel Approach to Solve k-Center Problems with Geographical Placement". In Service Operations and Logistics, and Informatics (SOLI), 2015 IEEE International Conference on, 31--36.Google Scholar
- Hochbaum, D. S., and D. B. Shmoys. 1985. "A Best Possible Heuristic for the k-Center Problem". Mathematics of Operations Research 10:180--184. Google ScholarDigital Library
- Jamin, S., C. Jin, A. R. Kurc, D. Raz, and Y. Shavitt. 2001. "Constrained Mirror Placement on the Internet". In INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Volume 1, 31--40.Google Scholar
- Kleinberg, J., and E. Tardos. 2005. Algorithm Design. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc. Google ScholarDigital Library
- MacQueen, J. 1967. "Some Methods for Classification and Analysis of Multivariate Observations". In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics, 281--297.Google Scholar
- Nguyen, A. M., J. Yosinski, and J. Clune. 2014. "Deep Neural Networks Are Easily Fooled: High Confidence Predictions for Unrecognizable Images". Computer Vision and Pattern Recognition abs/1412.1897.Google Scholar
- Selim, S. Z., and M. A. Ismail. 1984. "k-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality". IEEE Transactions on Pattern Analysis and Machine Intelligence 6 (1): 81--87. Google ScholarDigital Library
- Uhlig, T. 2015. Self-Replicating Individuals. München: Dr. Hut.Google Scholar
- Evaluation of the general applicability of Dragoon for the k-center problem
Recommendations
On the General Position Subset Selection Problem
Let $f(n,\ell)$ be the maximum integer such that every set of $n$ points in the plane with at most $\ell$ collinear contains a subset of $f(n,\ell)$ points with no three collinear. First we prove that if $\ell\leqslant O(\sqrt{n})$, then $f(n,\ell)\geqslant\...
Dragoon: an object-oriented notation supporting the reuse and distribution of Ada software
IRTAW '90: Proceedings of the fourth international workshop on Real-time Ada issuesAmong the more radical proposals for changes to the Ada standard in Ada9X are those advocating the introduction of "object-oriented" features exemplified by languages such as Smalltalk and Eiffel. DRAGOON is a language which supports the fundamental ...
Comments