Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs
Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs
复制标题
一类多项式优化问题与非均匀超图最大派系之间的联系
DOI：
10.1007/s10878-014-9798-x
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Yuping Yao
中科院分区：
文献类型：
--
作者：
Yangming Chang;Yuejian Peng;Yuping Yao
1965年，Motzkin和Straus提供了图中最大团的阶数与二次优化问题的全局解之间的联系，该解被称为拉格朗日函数。这种联系及其扩展在组合学和优化中都很有用。 2009年，Rota Bulò和Pelillo通过在一系列齐次多项式函数（不同于拉格朗日函数）的局部（全局）极小值与均匀超图的最大（最大）团之间建立一一对应关系，将Motzkin-Straus结果扩展到均匀超图。在本文中，我们研究了与非均匀超图相关的类似优化问题，并获得了其结果对非均匀超图的一些扩展。特别是，我们提供了一系列非齐次多项式函数的局部（全局）最小化器与超图的最大（最大）团之间的一一对应关系。主要结果的应用给出了完全超图的图兰密度的上限。证明中应用的方法遵循 Rota Bulò 和 Pelillo (2009) 中的方法。
In 1965, Motzkin and Straus provided a connection between the order of a maximum clique in a graphand a global solution of a quadratic optimization problem determined bywhich is called the Lagrangian function of. This connection and its extensions have been useful in both combinatorics and optimization. In 2009, Rota Bulò and Pelillo extended the Motzkin–Straus result to-uniform hypergraphs by establishing a one-to-one correspondence between local (global) minimizers of a family of homogeneous polynomial functions of degree(different from Lagrangian function) and the maximal (maximum) cliques of an-uniform hypergraph. In this paper, we study similar optimization problems related to non-uniform hypergraphs and obtain some extensions of their results to non-uniform hypergraphs. In particular, we provide a one-to-one correspondence between local (global) minimizers of a family of non-homogeneous polynomial functions and the maximal (maximum) cliques of-hypergraphs. An application of a main result gives an upper bound on the Turán density of complete-hypergraphs. The approach applied in the proof follows from the approach in Rota Bulò and Pelillo (2009).
登录
查看更多内容
DOI：
10.1016/s0166-218x(02)00386-4
发表时间：
2003-05
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
M. Budinich
通讯作者：
M. Budinich
影响因子：
1.1
作者：
P. Frankl;V. Rödl
通讯作者：
P. Frankl;V. Rödl
DOI：
10.1016/j.dam.2015.06.037
发表时间：
2013-12
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Yuejian Peng;Hao Peng;Qingsong Tang;Cheng Zhao
通讯作者：
Yuejian Peng;Hao Peng;Qingsong Tang;Cheng Zhao
影响因子：
1.6
作者：
S. R. Bulò;M. Pelillo
通讯作者：
S. R. Bulò;M. Pelillo
DOI：
10.2307/3615429
发表时间：
1984-03
期刊：
The Mathematical Gazette
影响因子：
--
作者：
Keith Lloyd
通讯作者：
Keith Lloyd