Loading...
Please wait, while we are loading the content...
Similar Documents
Volume computation for sparse boolean quadric relaxations
| Content Provider | arXiv |
|---|---|
| Author | Lee, Jon Skipper, Daphne |
| Date of Submission | 2018-10-16 |
| Abstract | Motivated by understanding the quality of tractable convex relaxations of intractable polytopes, Ko et al. gave a closed-form expression for the volume of a standard relaxation $\mathscr{Q}(G)$ of the boolean quadric polytope (also known as the (full) correlation polytope) $\mathscr{P}(G)$ of the complete graph $G=K_n$. We extend this work to structured sparse graphs, giving: (i) an efficient algorithm for $vol(\mathscr{Q}(G))$ when $G$ has bounded tree width, (ii) closed-form expressions (and asymptotic behaviors) for $vol(\mathscr{Q}(G))$ for all stars, paths, and cycles, and (iii) a closed-form expression for $vol(\mathscr{P}(G))$ for all cycles. Further, we demonstrate that when $G$ is a cycle, the simple relaxation $\mathscr{Q}(G)$ is a very close model for the much more complicated $\mathscr{P}(G)$. Additionally, we give some computational results demonstrating that this behavior of the cycle seems to extend to more complicated graphs. Finally, we speculate on the possibility of extending some of our results to cactii or even series-parallel graphs. |
| Related Links | https://arxiv.org/pdf/1703.02444.pdf |
| arXiv | 1703.02444 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics - Combinatorics Mathematics Integer programming $n$-dimensional polytopes Nonconvex programming Length, area, volume |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
