- Journal Article
Rights / licenseIn Copyright - Non-Commercial Use Permitted
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. Show more
Journal / seriesMathematical Programming
Pages / Article No.
SubjectRobust optimization; Combinatorial optimization; Matroid; Shortest path; Fault tolerant
Organisational unit09487 - Zenklusen, Rico / Zenklusen, Rico
NotesIt was possible to publish this article open access thanks to a Swiss National Licence with the publisher.
MoreShow all metadata