Connectivity via convexity: Bounds on the edge expansion in graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913529220562944 |
|---|---|
| author | Hrga, Timotej Siebenhofer, Melanie Wiegele, Angelika |
| author_facet | Hrga, Timotej Siebenhofer, Melanie Wiegele, Angelika |
| contents | Convexification techniques have gained increasing interest over the past decades. In this work, we apply a recently developed convexification technique for fractional programs by He, Liu and Tawarmalani (2024) to the problem of determining the edge expansion of a graph. Computing the edge expansion of a graph is a well-known, difficult combinatorial problem that seeks to partition the graph into two sets such that a fractional objective function is minimized.
We give a formulation of the edge expansion as a completely positive program and propose a relaxation as a doubly non-negative program, further strengthened by cutting planes. Additionally, we develop an augmented Lagrangian algorithm to solve the doubly non-negative program, obtaining lower bounds on the edge expansion. Numerical results confirm that this relaxation yields strong bounds and is computationally efficient, even for graphs with several hundred vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02526 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Connectivity via convexity: Bounds on the edge expansion in graphs Hrga, Timotej Siebenhofer, Melanie Wiegele, Angelika Optimization and Control Convexification techniques have gained increasing interest over the past decades. In this work, we apply a recently developed convexification technique for fractional programs by He, Liu and Tawarmalani (2024) to the problem of determining the edge expansion of a graph. Computing the edge expansion of a graph is a well-known, difficult combinatorial problem that seeks to partition the graph into two sets such that a fractional objective function is minimized. We give a formulation of the edge expansion as a completely positive program and propose a relaxation as a doubly non-negative program, further strengthened by cutting planes. Additionally, we develop an augmented Lagrangian algorithm to solve the doubly non-negative program, obtaining lower bounds on the edge expansion. Numerical results confirm that this relaxation yields strong bounds and is computationally efficient, even for graphs with several hundred vertices. |
| title | Connectivity via convexity: Bounds on the edge expansion in graphs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.02526 |