540. Combinatorial, conic and linear bounds for expansions in a graph
Invited abstract in session MD-13: Recent advances in optimization problems with cardinality constraints, stream Sparsity guarantee and cardinality-constrained (MI)NLPs.
Monday, 16:30-18:30Room: B100/6009
Authors (first author is the speaker)
| 1. | Akshay Gupte
|
| School of Mathematics, University of Edinburgh |
Abstract
We consider expansion problems in graphs, which are a class of fractional quadratic combinatorial optimization with cardinality constraints, and have applications in network science, coding theory etc. Edge expansion is a NP-hard cut problem that asks for finding the Cheeger constant (isoperimetric number) of a graph which is the smallest ratio of cut size to the size of the smaller partition. We derive some lower bounds in terms of graph diameter that are tight upto a constant factor and which lead to establishing the famous Mihail-Vazirani conjecture for all polytopes of diameter 2, e.g. asymmetric TSP, and a polynomial version of this conjecture for all 0-1 polytopes. Next, we obtain lower bounds through SDP relaxations and analyse their strength in terms of the spectrum of the graph Laplacian. In contrast, SOCP and LP relaxations give trivial lower bounds. Since the problem involves a cut function, lifted LP relaxations can be derived by using polymatroid inequalities for a submodular function and some disjunctive arguments. On the algorithmic side, we compare various root-finding algorithms for a parametric approach to the problem. Similar analyses can also be carried out for vertex expansion problems.
This is an extension of previous work in https://arxiv.org/abs/2403.04657 (ISCO 2024 and journal preprint).
Keywords
- Nonlinear mixed integer optimization
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers