4 Search Results for "Adjiashvili, David"

Document
DOI: 10.4230/LIPIcs.ESA.2024.74
Improved Approximations for Flexible Network Design

Authors: Dylan Hyatt-Denesik, Afrouz Jabal-Ameli, and Laura Sanità

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) fail. In particular, the set of edges (resp. vertices) of a given graph are here partitioned into safe and unsafe. The goal is to identify a minimum size subgraph that is 2-edge-connected (resp. 2-vertex-connected), and stay so whenever any of the unsafe elements gets removed. In this paper, we provide improved approximation algorithms for flexible network design problems, considering both edge-connectivity and vertex-connectivity, as well as connectivity values higher than 2. For the vertex-connectivity variant, in particular, our algorithm is the first with approximation factor strictly better than 2.
Cite as

Dylan Hyatt-Denesik, Afrouz Jabal-Ameli, and Laura Sanità. Improved Approximations for Flexible Network Design. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hyattdenesik_et_al:LIPIcs.ESA.2024.74,
  author =	{Hyatt-Denesik, Dylan and Jabal-Ameli, Afrouz and Sanit\`{a}, Laura},
  title =	{{Improved Approximations for Flexible Network Design}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{74:1--74:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.74},
  URN =		{urn:nbn:de:0030-drops-211456},
  doi =		{10.4230/LIPIcs.ESA.2024.74},
  annote =	{Keywords: Approximation Algorithms, Network Design, Flexible Connectivity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.5
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults

Authors: David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k-1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP.
Cite as

David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{adjiashvili_et_al:LIPIcs.SWAT.2022.5,
  author =	{Adjiashvili, David and Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver},
  title =	{{Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.5},
  URN =		{urn:nbn:de:0030-drops-161659},
  doi =		{10.4230/LIPIcs.SWAT.2022.5},
  annote =	{Keywords: graph algorithms, network design, fault tolerance, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.71
Robust Assignments via Ear Decompositions and Randomized Rounding

Authors: David Adjiashvili, Viktor Bindewald, and Dennis Michaels

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Many real-life planning problems require making a priori decisions before all parameters of the problem have been revealed. An important special case of such problem arises in scheduling and transshipment problems, where a set of jobs needs to be assigned to the available set of machines or personnel (resources), in a way that all jobs have assigned resources, and no two jobs share the same resource. In its nominal form, the resulting computational problem becomes the assignment problem. This paper deals with the Robust Assignment Problem (RAP) which models situations in which certain assignments are vulnerable and may become unavailable after the solution has been chosen. The goal is to choose a minimum-cost collection of assignments (edges in the corresponding bipartite graph) so that if any vulnerable edge becomes unavailable, the remaining part of the solution contains an assignment of all jobs. We develop algorithms and hardness results for RAP and establish several connections to well-known concepts from matching theory, robust optimization, LP-based techniques and combinations thereof.
Cite as

David Adjiashvili, Viktor Bindewald, and Dennis Michaels. Robust Assignments via Ear Decompositions and Randomized Rounding. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{adjiashvili_et_al:LIPIcs.ICALP.2016.71,
  author =	{Adjiashvili, David and Bindewald, Viktor and Michaels, Dennis},
  title =	{{Robust Assignments via Ear Decompositions and Randomized Rounding}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.71},
  URN =		{urn:nbn:de:0030-drops-62133},
  doi =		{10.4230/LIPIcs.ICALP.2016.71},
  annote =	{Keywords: robust optimization, matching theory, ear decomposition, randomized rounding, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.61
Non-Uniform Robust Network Design in Planar Graphs

Authors: David Adjiashvili

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

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.
Cite as

David Adjiashvili. Non-Uniform Robust Network Design in Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 61-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{adjiashvili:LIPIcs.APPROX-RANDOM.2015.61,
  author =	{Adjiashvili, David},
  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 =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.61},
  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}
}
  • Refine by Author
  • 3 Adjiashvili, David
  • 1 Bindewald, Viktor
  • 1 Hommelsheim, Felix
  • 1 Hyatt-Denesik, Dylan
  • 1 Jabal-Ameli, Afrouz
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Network flows
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Approximation algorithm
  • 1 Flexible Connectivity
  • 1 LP rounding
  • 1 Network Design
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2015
  • 1 2016
  • 1 2022
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact