Optimal Upgrading Schemes for Effective Shortest Paths in Networks
详细信息 查看全文
- 刊名：Lecture Notes in Computer Science
- 出版年：2016
- 出版时间：2016
- 年：2016
- 卷：9676
- 期：1
- 页码：406-420
- 全文大小：277 KB
- 参考文献：1.Álvarez-Miranda, E., Ljubić, I., Mutzel, P.: The rooted maximum node-weight connected subgraph problem. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 300–315. Springer, Heidelberg (2013)CrossRef
2.Ben-Ameur, W., Neto, J.: Acceleration of cutting-plane and column generation algorithms: applications to network design. Networks 49(1), 3–17 (2007)MathSciNet CrossRef MATH
3.Campbell, A., Lowe, T., Zhang, L.: Upgrading arcs to minimize the maximum travel time in a network. Networks 47(2), 72–80 (2006)MathSciNet CrossRef MATH
4.Costa, A.: A survey on benders decomposition applied to fixed-charge network design problems. Comput. OR 32(6), 1429–1450 (2005)MathSciNet CrossRef MATH
5.Dilkina, B., Gomes, C.P.: Solving connected subgraph problems in wildlife conservation. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 102–116. Springer, Heidelberg (2010)CrossRef
6.Dilkina, B., Lai, K.J., Gomes, C.P.: Upgrading shortest paths in networks. In: Achterberg, T., Beck, J.C. (eds.) CPAIOR 2011. LNCS, vol. 6697, pp. 76–91. Springer, Heidelberg (2011)CrossRef
7.Fischetti, M., Leitner, M., Ljubić, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out steiner trees: a node-based model for uniform edge costs. In: Workshop of the 11th DIMACS Implementation Challenge (2014)
8.Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1–3), 23–47 (2003)MathSciNet CrossRef MATH
9.Fischetti, M., Salvagnin, D.: An in-out approach to disjunctive optimization. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 136–140. Springer, Heidelberg (2010)CrossRef
10.Fournier, J.: Optimal paths, pp. 119–147. ISTE (2010)
11.Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: IJCAI (1), pp. 607–615 (1995)
12.Krumke, S., Marathe, M., Noltemeier, H., Ravi, R., Ravi, S., Sundaram, R., Wirth, H.: Improving minimum cost spanning trees by upgrading nodes. J. Algorithms 33(1), 92–111 (1999)MathSciNet CrossRef MATH
13.Magnanti, T., Mireault, P., Wong, R.: Tailoring benders decomposition for uncapacitated network design. In: Gallo, G., Sandi, C. (eds.) Netflow at Pisa, Mathematical Programming Studies, vol. 26, pp. 112–154. Springer, Heidelberg (1986)CrossRef
14.Paik, D., Sahni, S.: Network upgrading problems. Networks 26(1), 45–58 (1995)MathSciNet CrossRef MATH
15.Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis, Universitätsbibliothek (2003)
16.Vassilevska, V.: Efficient algorithms for path problems in weighted graphs. Ph.D. thesis, Carnegie Mellon University, August 2008 - 作者单位：Eduardo Álvarez-Miranda (14)
Martin Luipersbeck (15)
Markus Sinnl (15)
14. Department of Industrial Engineering, Universidad de Talca, Curicó, Chile
15. Department Statistics and Operations Research, University of Vienna, Vienna, Austria - 丛书名：Integration of AI and OR Techniques in Constraint Programming
- ISBN：978-3-319-33954-2
- 刊物类别：Computer Science
- 刊物主题：Artificial Intelligence and Robotics
Computer Communication Networks
Software Engineering
Data Encryption
Database Management
Computation by Abstract Devices
Algorithm Analysis and Problem Complexity - 出版者：Springer Berlin / Heidelberg
- ISSN：1611-3349
- 卷排序：9676
文摘
In this paper, a generalization of a recently proposed optimal path problem concerning decisions for improving connectivity is considered [see 6]. Each node in the given network is associated with a connection delay which can be reduced by implementing upgrading actions. For each upgrading action a cost must be paid, and the sum must satisfy a budget constraint. Given a fixed budget, the goal is to choose a set of upgrading actions such that the total delay of establishing paths among predefined node pairs is minimized. This model has applications in areas like multicast communication planning and wildlife reserve design.