Seri Khoury

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2024-158

August 5, 2024

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-158.pdf

A graph is a mathematical construct that models pairwise relations between objects through nodes (or vertices) and edges (also known as links) that connect these nodes. Due to the capacity of graphs to encapsulate a wide range of combinatorial structures, there has been a vibrant pursuit of developing fast and efficient graph algorithms to address a broad spectrum of graph-related problems, including covering and packing problems, clustering problems, distance computation, and symmetry breaking.

This thesis explores approximation algorithms for graph problems. The first part is dedicated to distance computation problems, where we present several new hardness of approximation results across different models of computation, including the centralized, distributed, and dynamic models.

The second part focuses on symmetry-breaking problems in Distributed Computing. Here, we devise efficient approximation algorithms for Maximum Independent Set and Maximum Matching in regular graphs, and introduce new hardness of approximation results for Maximum Independent Set.

Advisors: Shafi Goldwasser

---

BibTeX citation:

@phdthesis{Khoury:EECS-2024-158,
    Author= {Khoury, Seri},
    Title= {Hardness of Approximation Across Different Models of Computation},
    School= {EECS Department, University of California, Berkeley},
    Year= {2024},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-158.html},
    Number= {UCB/EECS-2024-158},
    Abstract= {A graph is a mathematical construct that models pairwise relations between objects through nodes (or vertices) and edges (also known as links) that connect these nodes. Due to the capacity of graphs to encapsulate a wide range of combinatorial structures, there has been a vibrant pursuit of developing fast and efficient graph algorithms to address a broad spectrum of graph-related problems, including covering and packing problems, clustering problems, distance computation, and symmetry breaking.

This thesis explores approximation algorithms for graph problems. The first part is dedicated to distance computation problems, where we present several new hardness of approximation results across different models of computation, including the centralized, distributed, and dynamic models.

The second part focuses on symmetry-breaking problems in Distributed Computing. Here, we devise efficient approximation algorithms for Maximum Independent Set and Maximum Matching in regular graphs, and introduce new hardness of approximation results for Maximum Independent Set.},
}

EndNote citation:

%0 Thesis
%A Khoury, Seri 
%T Hardness of Approximation Across Different Models of Computation
%I EECS Department, University of California, Berkeley
%D 2024
%8 August 5
%@ UCB/EECS-2024-158
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-158.html
%F Khoury:EECS-2024-158