论文标题
带有单位系数的二次函数图的凸壳：甚至轮子和完整的拆分图
Convex Hulls for Graphs of Quadratic Functions With Unit Coefficients: Even Wheels and Complete Split Graphs
论文作者
论文摘要
我们研究二次函数图的凸壳$ f（\ mathbf {x}）= \ sum_ {ij \ in e} x_ix_j $，其中的总和与vertex set $ \ \ \ {1，\ dots，n \} $的Gragr $ g $的边缘集上方。使用Gupte等人提出的方法。 （离散优化$ \ textbf {36} $，2020，100569），我们使用附加变量$ y_ {ij} $，$ 1 \ leq i <j \ leq n $调查最小扩展公式，代表产品$ x_ix_j $。基本思想是识别布尔二次多型的一组方面，足以表征给定图的凸船体。我们的主要结果是扩展配方，即基础图$ G $是均匀的车轮或完整的拆分图。
We study the convex hull of the graph of a quadratic function $f(\mathbf{x})=\sum_{ij\in E}x_ix_j$, where the sum is over the edge set of a graph $G$ with vertex set $\{1,\dots,n\}$. Using an approach proposed by Gupte et al. (Discrete Optimization $\textbf{36}$, 2020, 100569), we investigate minimal extended formulations using additional variables $y_{ij}$, $1\leq i<j\leq n$, representing the products $x_ix_j$. The basic idea is to identify a set of facets of the Boolean Quadric Polytope which is sufficient for characterizing the convex hull for the given graph. Our main results are extended formulations for the cases that the underlying graph $G$ is either an even wheel or a complete split graph.
