Edge expansion of a graph: SDP-based computational strategies
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912727060971520 |
|---|---|
| author | Gupte, Akshay Siebenhofer, Melanie Wiegele, Angelika |
| author_facet | Gupte, Akshay Siebenhofer, Melanie Wiegele, Angelika |
| contents | Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relaxation first to reduce the search space considerably. The problem is then transformed into instances of max-cut problems, which are solved with an SDP-based state-of-the-art solver. Our second variant to compute the edge expansion uses Dinkelbach's algorithm for fractional programming. This is, we have to solve a parametrized optimization problem and again we use semidefinite programming to obtain solutions of the parametrized problems. Numerical results demonstrate that with our algorithms one can compute the edge expansion on graphs up to 400 vertices in a routine way, including instances where standard branch-and-cut solvers fail. To the best of our knowledge, these are the first SDP-based solvers for computing the edge expansion of a graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04657 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Edge expansion of a graph: SDP-based computational strategies Gupte, Akshay Siebenhofer, Melanie Wiegele, Angelika Optimization and Control 90C27, 90C22, 90C32 Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relaxation first to reduce the search space considerably. The problem is then transformed into instances of max-cut problems, which are solved with an SDP-based state-of-the-art solver. Our second variant to compute the edge expansion uses Dinkelbach's algorithm for fractional programming. This is, we have to solve a parametrized optimization problem and again we use semidefinite programming to obtain solutions of the parametrized problems. Numerical results demonstrate that with our algorithms one can compute the edge expansion on graphs up to 400 vertices in a routine way, including instances where standard branch-and-cut solvers fail. To the best of our knowledge, these are the first SDP-based solvers for computing the edge expansion of a graph. |
| title | Edge expansion of a graph: SDP-based computational strategies |
| topic | Optimization and Control 90C27, 90C22, 90C32 |
| url | https://arxiv.org/abs/2403.04657 |