License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.61
URN: urn:nbn:de:0030-drops-52948
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5294/
Go to the corresponding LIPIcs Volume Portal

Adjiashvili, David

Non-Uniform Robust Network Design in Planar Graphs

pdf-format:
4.pdf (0.5 MB)

Abstract

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 Bulk-Robustness, a model recently introduced (Adjiashvili, Stiller, Zenklusen 2015) for addressing the need to model non-uniform failure patterns in systems.

We significantly extend the techniques used by Adjiashvili et al. 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.

BibTeX - Entry

@InProceedings{adjiashvili:LIPIcs:2015:5294,
  author =	{David Adjiashvili},
  title =	{{Non-Uniform Robust Network Design in Planar Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{61--77},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5294},
  URN =		{urn:nbn:de:0030-drops-52948},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.61},
  annote =	{Keywords: Robust optimization, Network design, Planar graph, Approximation algorithm, LP rounding}
}

Keywords: Robust optimization, Network design, Planar graph, Approximation algorithm, LP rounding
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI