Technical Report MSC-2021-14

Title: Fault Tolerant Max-Cut
Authors: Noa Marelly
Supervisors: Keren Censor-Hillel and Roy Schwartz
PDFCurrently 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.

CopyrightThe 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 (, 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

Computer science department, Technion