基于现代凸优化的图算法。
cvxgraphalgs的Python项目详细描述
CVX图算法
简介
Modern convex optimization-based graph algorithms.
凸优化为精确和优化设计提供了一个令人兴奋的新方向。 近似图算法。然而，这些算法在 由于在快速求解大型凸规划方面的局限性而进行的实践。 尽管如此，基于凸优化的图算法还是取得了令人印象深刻的效果 理论上的表现，往往能提供优美的几何解释。 这个包实现了其中一些算法，并提供了相应的 测试性能的图形生成器——希望能突出显示它的简单性， 优雅和有效这些可以为许多现实世界的问题。
详细信息
在这个包中，我们提供了以下算法的实现。注意 基于凸优化的算法以粗体显示，参考文献为 在可用时提供。
这个包还提供了从planted 独立集分布与随机块模型。
- 最大割问题
- goemans-williamson max-cut算法[1]
- 随机最大割算法
- 贪心最大割算法
- 独立集算法
- 基于原油sdp的独立集[2]
- 贪婪独立集算法
- 独立集的谱算法
安装和使用
您可以直接从python包索引（pypi）安装它。
pip install cvxgraphalgs
下面，我们将展示如何在图上运行goemans-williamson max-cut算法 从随机块模型分布中提取。有关更多示例，请浏览 Jupyter笔记本电脑和软件包文档一起提供 here。
>>> import cvxgraphalgs as cvxgr
>>> graph, _ = cvxgr.generators.bernoulli_planted_independent(
... size=50, independent_size=15, probability=0.5
... )
>>> recovered = cvxgr.algorithms.crude_sdp_independent_set(graph)
>>> len(recovered)
15
参考文献
[1]：戈曼斯、米歇尔X和大卫P威廉森。”改进逼近 半定的最大割与可满足问题的算法 编程，“美国计算机学会期刊（jacm）42，第6期（1995）：1115-1145.
[2]：麦肯齐、西奥、赫米什·梅塔和卢卡·特雷维森。”一种新的算法 稳健半随机独立集问题“arxiv:1808.03633（2018）。
欢迎加入QQ群-->： 979659372
