Bulk-Robust combinatorial optimization

详细信息    查看全文

• 作者：David Adjiashvili (1)
  Sebastian Stiller (2)
  Rico Zenklusen (3) (4)
  
  1. Institute for Operations Research ; ETH Z眉rich ; R盲mistrasse 101 ; 8092聽 ; Zurich ; Switzerland
  2. Department of Mathematics ; Berlin Institute of Technology ; Strasse des 17. Juni 136 ; 10623聽 ; Berlin ; Germany
  3. Department of Mathematics ; ETH Z眉rich ; R盲mistrasse 101 ; 8092聽 ; Zurich ; Switzerland
  4. Department of Applied Mathematics and Statistics ; Johns Hopkins University ; 3400 N. Charles Street ; Baltimore ; MD ; 21218 ; USA
  
• 关键词：Robust optimization ; Combinatorial optimization ; Matroid ; Shortest path ; Fault tolerant ; 90C27 ; 90C59 ; 68W25 ; 05B35
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：149
• 期：1-2
• 页码：361-390
• 全文大小：435 KB
• 参考文献：1. Adjiashvili, D.: Structural Robustness in Combinatorial Optimization. Ph.D. thesis, Z眉rich, Switzerland (2012)
  2. Adjiashvili, D.: Fault-tolerant shortest paths-beyond the uniform failure model. 301.6299" class="a-plus-plus">arXiv:1301.6299 (2013, preprint)
  3. Adjiashvili, D., Zenklusen, R.: An s-t connection problem with adaptability. Discret. Appl. Math. 159, 695鈥?05 (2011) CrossRef
  4. Aissi, H., Bazgan, C., Vanderpooten, D.: Minmax and minmax regret versions of combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197(2), 427鈥?38 (2009) CrossRef
  5. Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, Giancarlo, Bovet, Daniel, Di Battista, Giuseppe (eds.) Algorithms and Complexity, Lecture Notes in Computer Science, vol. 1203, pp. 288鈥?98. Springer, Berlin/Heidelberg (1997)
  6. Berger, A., Bonifaci, V., Grandoni, F., Sch盲fer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Math. Program. Ser. A 128, 355鈥?72 (2009) 307-4" target="_blank" title="It opens in new window">CrossRef
  7. Bernstein, A.: A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 742鈥?55 (2010)
  8. Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53, 464鈥?01 (2011) 37/080734510" target="_blank" title="It opens in new window">CrossRef
  9. Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. Ser. B 98, 2003 (2003) 3-0396-4" target="_blank" title="It opens in new window">CrossRef
  10. Catanzaro, D., Labb, M., Salazar-Neumann, M.: Reduction approaches for robust shortest path problems. Comput. Oper. Res. 38(11), 1610鈥?619 (2011) CrossRef
  11. Chekuri, C., Vondr谩k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 575鈥?84 (2010)
  12. Chekuri, C., Vondr谩k, J., Zenklusen. R.: Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the 21st Annual ACM鈥揝IAM Symposium on Discrete Algorithms (SODA), pp. 1080鈥?097 (2011)
  13. Chekuri, C., Vondr谩k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 783鈥?92 (2011)
  14. Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput. 30, 292鈥?01 (2000) 37/S009753979833920X" target="_blank" title="It opens in new window">CrossRef
  15. Dhamdhere, K., Goyal, V., Ravi, R., Singh, M.: How to pay, come what may: approximation algorithms for demand-robust covering problems. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 367鈥?76 (2005, October)
  16. Dodis, Y., Khanna, S.: Design networks with bounded pairwise distance. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 750鈥?59, New York, NY, USA (1999)
  17. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45, 634鈥?52 (July 1998)
  18. Feige, U., Jain, K., Mahdian, M., Mirrokni, V.: Robust combinatorial optimization with exponential scenarios. In: Fischetti, Matteo, Williamson, David (eds.) Proceedings of Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science, vol. 4513, pp. 439鈥?53. Springer, Berlin (2007) 3-540-72792-7_33" target="_blank" title="It opens in new window">CrossRef
  19. Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, pp. 570鈥?79. Washington, DC, USA, (2011)
  20. Gabow, H.N., Goemans, M.X., Tardos, 脡., Williamson, D.P.: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53(4), 345鈥?57 (2009) CrossRef
  21. Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co, New York (1990)
  22. Golovin, D., Goyal, V., Ravi, R.: Pay today for a rainy day: improved approximation algorithms for demand-robust min-cut and shortest path problems. In: Durand, Bruno, Thomas, Wolfgang (eds.) Proceedings of 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, vol. 3884, pp. 206鈥?17. Springer, Berlin (2006)
  23. Grandoni, F., Ravi, R., Singh, M., Zenklusen, R.: New approaches to multi-objective optimization. Math. Program. Ser. A., Available online at http://link.springer.com/article/10.1007 (to appear)
  24. Grandoni, F., Vassilevska Williams, V.: Improved distance sensitivity oracles via fast single-source replacement paths. In: FOCS, pp. 748鈥?57 (2012)
  25. Hassin, R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17, 36鈥?2 (1992) 36" target="_blank" title="It opens in new window">CrossRef
  26. Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks 40, 97鈥?11 (2002) 39" target="_blank" title="It opens in new window">CrossRef
  27. Khandekar, R., Kortsarz, G., Mirrokni, V., Salavatipour, M.: Two-stage robust network design with exponential scenarios. In: Halperin, Dan, Mehlhorn, Kurt (eds.) ESA 2008, Lecture Notes in Computer Science, vol. 5193, pp. 589鈥?00. Springer, Berlin/Heidelberg (2008)
  28. Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer, Boston (1997) CrossRef
  29. Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the Twentieth Annual ACM鈥揝IAM Symposium on Discrete Algorithms, SODA鈥?9, pp. 545鈥?54, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics
  30. Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177鈥?88 (1978) 3.3.177" target="_blank" title="It opens in new window">CrossRef
  31. Olver, N.-K.: Robust network design. Ph.D. thesis. Montreal, Que., Canada (2010)
  32. Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: FOCS鈥?0: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 86鈥?2, Washington, DC, USA (2000)
  33. Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem. In: Algorithm Theory鈥擲WAT鈥?6, volume 1097 of Lecture Notes in Computer Science, pp. 66鈥?5. Springer, Berlin (1996)
  34. Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt, H.B.: Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of the twenty-fifth annual ACM Symposium on the Theory of Computing, STOC鈥?3, pp. 438鈥?47 (1993)
  35. Raz R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC鈥?7, ACM, pp. 475鈥?84 (1997)
  36. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
  37. Sorkin, G.B., Steger, A., Zenklusen, R.: A tight bound on the collection of edges in MSTs of induced subgraphs. J. Combin. Theory Ser. B 99, 428鈥?35 (2009) CrossRef
  38. Vassilevska Williams, V.: Faster replacement paths. In: Proceedings of the 22rd Annual ACM鈥擲IAM Symposium on Discrete Algorithms (SODA), pp. 1337鈥?346 (2011)
  39. Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 645鈥?54 (2010)
  40. Warburton, A.: Approximation of pareto optima in multiple-objective, shortest-path problems. Oper. Res. 35(1), 70鈥?9 (1987) 35.1.70" target="_blank" title="It opens in new window">CrossRef
  41. Yu, G., Yang, J.: On the robust shortest path problem. Comput. Oper. Res. 25(6), 457鈥?68 (1998) 305-0548(97)00085-3" target="_blank" title="It opens in new window">CrossRef
  42. Zenklusen, R.: Matching interdiction. Discret. Appl. Math. 158(15), 1676鈥?690 (2010) CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial optimization features a highly nonuniform failure model. Instead of an interdiction budget, Bulk-Robust counterparts provide an explicit list of interdiction sets, comprising the admissible set of scenarios, thus allowing to model correlations between failures of different components in the system, interdiction sets of variable cardinality and more. The resulting model is suitable for capturing failures of complex structures in the system. We provide complexity results and approximation algorithms for Bulk-Robust counterparts of the Minimum Matroid Basis problems and the Shortest Path problem. Our results rely on various techniques, and outline the rich and heterogeneous combinatorial structure of Bulk-Robust optimization.