Abstract
In the Minimum Bounded-Degree Spanning Tree Problem we want to find a minimum cost spanning tree that satisfies given degree bounds. For this problem a very good quality solution can be found using the iterative relaxation technique of Singh and Lau STOC’07: the cost will not be worse than the cost of the optimal solution, and the degree bounds will be violated by at most one. This paper reports on the experimental comparison of this state-of-art approximation algorithm with standard, although well-tuned meta-heuristics. We have implemented the Iterative Relaxation algorithm of Singh and Lau and speeded it up using several heuristics including row generation and combinatorial LP pivoting. On the other hand, as the heuristic point of reference we have chosen local search techniques in a Simulated Annealing framework, where we allow the violation of degree bounds by one. In such setting there are two natural objectives for comparison: the cost of the solution, and the number of violated degree bounds. If we keep the number of violated constraints fixed in both algorithms then Iterative Rounding usually outperforms Simulated Annealing by several percents.
Research was supported by the ERC StG project PAAl no. 259515.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Andrade, R., Lucena, A., Maculan, N.: Using Lagrangian dual information to generate degree constrained spanning trees. Discrete Appl. Math. 154(5), 703–717 (2006), http://www.sciencedirect.com/science/article/pii/S0166218X0500301X
Boldon, B., Deo, N., Kumar, N.: Minimum-weight degree-constrained spanning tree problem: Heuristics and implementation on an SIMD parallel machine. Parallel Comput. 22(3), 369–382 (1996)
CPLEX, I.I.: High performance mathematical programming engine, http://www-01.ibm.com/software/integration/optimization/cplex-optimizer
Deo, N., Hakimi, S.: The shortest generalized hamiltonian tree. In: Proceedings of the 6th Annual Allerton Conference, pp. 879–888. University of Illinois, Illinois (1968)
Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1(1), 127–136 (1971)
Furer, M., Raghavachari, B.: Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithm 17(3), 409–423 (1994)
Goemans, M.X.: Minimum bounded degree spanning trees. In: FOCS 2006, pp. 273–282. IEEE Computer Society, Los Alamitos (2006)
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)
Krishnamoorthy, M., Ernst, A.T., Sharaiha, Y.M.: Comparison of algorithms for the degree constrained minimum spanning tree. J. Heuristics 7(6), 587–611 (2001)
Lau, L.C., Ravi, R., Singh, M.: Iterative methods in combinatorial optimization. Cambridge University Press, Cambridge (2011)
Library for Efficient Modeling and Optimization in Networks (LEMON), http://lemon.cs.elte.hu
Narula, S., Ho, C.: Degree-constrained minimum spanning tree. Comput. Oper. Res. 7, 239–249 (1980)
Practical Approximation Algorithms Library (PAAL), http://paal.mimuw.edu.pl
Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Many birds with one stone: Multi-objective approximation algorithms. In: STOC 1993, pp. 438–447. ACM, New York (1993), http://doi.acm.org/10.1145/167088.167209
Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC 2007, pp. 661–670. ACM, New York (2007)
Zahrani, M.S., Loomes, M.J., Malcolm, J.A., Albrecht, A.A.: A local search heuristic for bounded-degree minimum spanning trees. Eng. Optimiz. 40(12), 1115–1135 (2008), http://www.tandfonline.com/doi/abs/10.1080/03052150802317440
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bernáth, A., Ciebiera, K., Godlewski, P., Sankowski, P. (2014). Implementation of the Iterative Relaxation Algorithm for the Minimum Bounded-Degree Spanning Tree Problem. In: Gudmundsson, J., Katajainen, J. (eds) Experimental Algorithms. SEA 2014. Lecture Notes in Computer Science, vol 8504. Springer, Cham. https://doi.org/10.1007/978-3-319-07959-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-07959-2_7
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07958-5
Online ISBN: 978-3-319-07959-2
eBook Packages: Computer ScienceComputer Science (R0)