Non-Uniform Robust Network Design in Planar Graphs

Autor:	Adjiashvili, David
Rok vydání:	2015
Předmět:	Mathematics - Optimization and Control Computer Science - Data Structures and Algorithms I.1.2 G.2.2 G.1.6
Druh dokumentu:	Working Paper
Popis:	Robust optimization is concerned with constructing solutions that remain feasible also when a limited number of resources is removed from the solution. Most studies of robust combinatorial optimization to date made the assumption that every resource is equally vulnerable, and that the set of scenarios is implicitly given by a single budget constraint. This paper studies a robustness model of a different kind. We focus on \textbf{bulk-robustness}, a model recently introduced~\cite{bulk} for addressing the need to model non-uniform failure patterns in systems. We significantly extend the techniques used in~\cite{bulk} to design approximation algorithm for bulk-robust network design problems in planar graphs. Our techniques use an augmentation framework, combined with linear programming (LP) rounding that depends on a planar embedding of the input graph. A connection to cut covering problems and the dominating set problem in circle graphs is established. Our methods use few of the specifics of bulk-robust optimization, hence it is conceivable that they can be adapted to solve other robust network design problems. Comment: 17 pages, 2 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1504.05009 Zobrazit plný text záznamu View this record from Arxiv