| TR#: | MSC-2021-14 |
| Class: | MSC |
| Title: | Fault Tolerant Max-Cut |
| Authors: | Noa Marelly |
| Supervisors: | Keren Censor-Hillel and Roy Schwartz |
| Currently accessibly only within the Technion network | |
| Abstract: | In this work, we initiate the study of fault tolerant Max-Cut, where given an edge-weighted undirected graph G=(V,E), the goal is to find a cut S, that maximizes the total weight of edges that cross S even after an adversary removes k vertices from G. We consider two types of adversaries: an adaptive adversary that sees the outcome of the random coin tosses used by the algorithm, and an oblivious adversary that does not. For any constant number of failures k we present an approximation of 0.878 against an adaptive adversary and of αGW (approximately 0.8786) against an oblivious adversary (here αGW is the approximation achieved by the random hyperplane algorithm of [Goemans-Williamson J. ACM `95]). Additionally, we present a hardness of approximation of αGW against both types of adversaries, rendering our results (virtually) tight. The non-linear nature of the fault tolerant objective makes the design and analysis of algorithms harder when compared to the classic Max-Cut. Hence, we employ approaches ranging from multi-objective optimization to LP duality and the ellipsoid algorithm to obtain our results. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2021/MSC/MSC-2021-14), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the MSC technical reports of 2021
To the main CS technical reports page