A tolerance-based heuristic approach for the weighted independent set problem

详细信息    查看全文

• 作者：B. I. Goldengorin (1) (2)
  D. S. Malyshev (1) (3) (4)
  P. M. Pardalos (1) (5)
  V. A. Zamaraev (1) (3) (4)
  
  1. Laboratory of Algorithms and Technologies for Network Analysis ; National Research University Higher School of Economics ; 136 Rodionova str. ; Nizhny Novgorod ; 603093 ; Russia
  2. Department of Mathematics ; Subdepartment of Higher Mathematics ; National Research University Higher School of Economics ; 26 Shabolovka str. ; Moscow ; 119049 ; Russia
  3. Department of Applied Mathematics and Informatics ; National Research University Higher School of Economics ; 25/12 Bolshaya Pecherskaya str. ; Nizhny Novgorod ; 603155 ; Russia
  4. Department of Mathematical Logic and Higher Algebra ; Lobachevsky State University of Nizhny Novgorod ; 23 Gagarina av. ; Nizhny Novgorod ; 603950 ; Russia
  5. Department of Industrial and System Engineering ; Faculty of Engineering ; Center for Applied Optimization ; University of Florida ; 401 Weil Hall ; P.O. Box 116595 ; Gainesville ; FL ; 32611-6595 ; USA
  
• 关键词：Combinatorial optimization ; Independent set problem ; Heuristics ; Notion of a tolerance
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：29
• 期：2
• 页码：433-450
• 全文大小：371 KB
• 参考文献：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.