参考文献:1. Aiello W, Chung F, Lu L (2000) A random graph model for power-law graphs. Exp Math 10:53鈥?6 CrossRef 2. Balas E, Saltzman M (1991) An algorithm for the three-index assignment problem. Oper Res 39:150鈥?61 CrossRef 3. Barabasi A, Reka A (1999) Emergence of scaling in random networks. Science 286:509鈥?12 CrossRef 4. Bekker H, Braad E, Goldengorin B (2005) Selecting the roots of a small system of polynomial equations by tolerance based matching. Lect Notes Comput Sci 3503:610鈥?13 CrossRef 5. Bron C, Kerbosch J (1973) Finding all cliques of an undirected graph. Commun ACM 16:575鈥?77 CrossRef 6. Bollobas B, Riordan R, Spencer J, Tusnady G (2001) The degree sequence of a scale-free random graph process. Random Struct Algorithms 18:279鈥?90 CrossRef 7. Boyko V, Goldengorin B, Kuzmenko V (2006) Tolerance-based algorithms. Theory Optim Decis 5:98鈥?04 (in Ukrainian) 8. Chen C, Kuo M, Sheu J (1988) An optimal time algorithm for finding a maximum weight independent set in a tree. BIT Numer Math 28:353鈥?56 CrossRef 9. Cormen T, Leiserson C, Rivest R, Stein C (2001) Introduction of algorithms, 2nd edn. MIT Press/McGraw-Hill, Cambridge 10. Ernst C, Dong C, Jager G, Richter D, Molitor P (2010) Finding good tours for huge euclidean TSP instances by iterative backbone contraction. In: AAIM, pp 119鈥?30 11. Faloutsos M, Faloutsos P, Faloutsos C (1999) On the power-law relationships of the internet topology. Comput Commun Rev 29:251鈥?62 CrossRef 12. Gal T, Greenberg H (1997) Advances in sensitivity analysis and parametric programming. Kluwer Academic Publishers, New York CrossRef 13. Germs R, Goldengorin B, Turkensteen M (2012) Lower tolerance-based branch and bound algorithms for the ATSP. Comput Oper Res 39:291鈥?98 CrossRef 14. Ghosh D, Goldengorin B, Gutin G, Jager G (2007) Tolerance-based greedy algorithms for the traveling salesman problem. In: Bapat R, Das A, Partasaraty T, Neogy S (eds) Mathematical programming and game theory for decision making. World Scientific Publishing, Singapore 15. Goldengorin B, Jager G, Molitor P (2006) Tolerances applied in combinatorial optimization. J Comput Sci 2:716鈥?34 CrossRef 16. Greenberg H (1998) An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: Woodruff D (ed) Advances in computational and stochastic optimization, logic programming and heuristic search. Kluwer Academic Publishers, New York, pp 97鈥?48 17. Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur J Oper Res 126:106鈥?30 CrossRef 18. Helsgaun K (2009) General \(k\) -opt submoves for the Lin-Kernighan TSP heuristic. Math Program Comput 1:119鈥?63 CrossRef 19. Jager G, Molitor P (2008) Algorithms and experimental study for the traveling salesman problem of second order. In: COCOA, pp 211鈥?24 20. Kruskal J (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7(1):48鈥?0 CrossRef 21. Kumar R, Raghavan P, Rajagopalan S, Tomkins A (1999) Trawing the Web for emerging cyber-communities. Comput Netw 7:1481鈥?493 CrossRef 22. Murty K (1968) An algorithm for ranking all the assignments in order of increasing cost. Oper Res 16: 682鈥?87 CrossRef 23. Ramaswamy R, Orlin J, Chakravarti N (2005) Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs. Math Program 102:355鈥?69 CrossRef 24. Reinfeld N, Vogel W (1965) Mathematical programming. Prentice Hall, Englewood Cliffs 25. Shier D, Witzgall C (1980) Arc tolerances in minimum-path and network flow problems. Networks 10: 277鈥?91 CrossRef 26. Sotskov Y, Leontev V, Gordeev E (1995) Some concepts of stability analysis in combinatorial optimization. Discret Appl Math 58:169鈥?90 CrossRef 27. Tarjan R (1982) Sensitivity analysis of minimum spanning trees and shortest path trees. Inf Process Lett 14:30鈥?3 CrossRef 28. Turkensteen M, Ghosh D, Goldengorin B, Sierksma G (2008) Tolerance-based branch and bound algorithms for the ATSP. Eur J Oper Res 189:775鈥?88 CrossRef 29. Van der Poort E, Libura M, Sierksma G, Van der Veen J (1999) Solving the \(k\) -best traveling salesman problem. Comput Oper Res 26:409鈥?25 CrossRef 30. Volgenant A (2006) An addendum on sensitivity analysis of the optimal assignment. Eur J Oper Res 169:338鈥?39 CrossRef
刊物类别:Mathematics and Statistics
刊物主题:Mathematics Combinatorics Convex and Discrete Geometry Mathematical Modeling and IndustrialMathematics Theory of Computation Optimization Operation Research and Decision Theory
出版者:Springer Netherlands
ISSN:1573-2886
文摘
The notion of a tolerance is a helpful tool for designing approximation and exact algorithms for solving combinatorial optimization problems. In this paper we suggest a tolerance-based polynomial heuristic algorithm for the weighted independent set problem. Several computational experiments show that our heuristics works very well on graphs of a small density.