文件名称：SAGE算法代码matlab-brownian-rounding:布朗四舍五入
文件大小：470KB
文件格式：ZIP
更新时间：2024-06-22 05:35:38
系统开源
SAGE算法代码matlab 粘性布朗舍入及其在约束满足问题中的应用 这是论文“粘性布朗舍入及其在约束满足问题中的应用”中描述的算法的实现，用于获取近似因子。 1. 布朗四舍五入的扩展 我们考虑以下扩展： 1.1. 带减速的布朗舍入1.2. 高维布朗舍入 1.1. 带减速的布朗舍入 在这里，我们描述了我们如何以数值方式获得引入的舍入算法的近似因子。 首先，让我们定义什么是配置。 让 成为 SDP 松弛的解向量。 这些向量大小的每个子集形成一维空间配置。 基于我们想要解决的问题，我们只对 的特定值感兴趣。 例如，在我们考虑的所有二元 Max-2-CSP 问题中，我们对由 和 其他两个向量组成的 3 维配置感兴趣。 这个想法是对于给定的配置，我们可以找到它在 SDP 松弛中的贡献（基于松弛的目标）。 此外，我们能够计算舍入过程的期望值。 因此，我们确定了此特定配置的舍入的预期近似比率。 通过对感兴趣问题的所有可行配置（例如，Max-Cut）重复此过程，并取它们的最小值，我们将找到针对所有实例的舍入算法在该问题上的预期近似因子。 为了枚举所有配置，我们需要离散化可能配置的空间。 可以根据我们
【文件预览】：
brownian-rounding-master
----SOS proofs()
--------g2_approx.m(3KB)
--------g3_approx_polynomials.docx(41KB)
--------g2_approx_polynomials.docx(32KB)
--------g3_D.m(2KB)
--------g2_D.m(1KB)
--------g3_approx.m(2KB)
--------g3_D_polynomials.docx(18KB)
----brownian_simulation.sage(2KB)
----README.tex.md(6KB)
----tex()
--------49e9b6e32c4d2a82903e7187c904df9b.svg(19KB)
--------d0f8ef7494681f6b5311e319113b1263.svg(7KB)
--------f19c5e6eb3a3636eb27cae3071665f74.svg(13KB)
--------4d8443b72a1de913b4a3995119296c90.svg(4KB)
--------64f56542d8c96b6573f52b8e6135215f.svg(6KB)
--------alg1.png(286KB)
--------39eeb375dd63994e249344baa2ae2eb4.svg(9KB)
--------c2c1ffc64fafa0a3c1108be047c4c155.svg(9KB)
--------607e620664d7cab446228b1147ec906e.svg(4KB)
--------9b43195e4a51831d582b0cb8a47e76ed.svg(14KB)
--------9b325b9e31e85137d1de765f43c0f8bc.svg(3KB)
--------f3778000bfc0ee846c972a558e10d161.svg(20KB)
--------38078c5daea8c0c56efcfd83cf0afe4d.svg(5KB)
--------e53bb0b68d306e5a270fe0f587e42ab8.svg(3KB)
--------e88edbf4c389f77c73137df563d51056.svg(4KB)
--------3a0999540a345758e8259a30f523c1c9.svg(4KB)
--------a6bcb51f5330e091bc682b94229d5125.svg(15KB)
--------a50c3a6cce0c5b640cc5bef1d62b99bd.svg(3KB)
--------a47c8a76f36899d4f249512efb68d4dc.svg(26KB)
--------3e7d30640ead2b8786a1d3fcfc827431.svg(9KB)
--------96235a90d058ab0f9bc16c8a1a37aa49.svg(3KB)
--------23aa6ff2687d438a348158229e09f895.svg(8KB)
--------ee28c74bfb67b15c2001f65843f8c94a.svg(2KB)
--------61df49547d4a5eea21a56dd1c368109c.svg(7KB)
--------cda19f7637b915e58b1f45d3697c3b51.svg(9KB)
--------1924b0e737a1c5c085f6e7f1b0fa4840.svg(4KB)
--------9fc20fb1d3825674c6a279cb0d5ca636.svg(5KB)
--------2103f85b8b1477f430fc407cad462224.svg(3KB)
--------4e439908eadd690a655edba5605a50a7.svg(15KB)
--------3cf4fbd05970446973fc3d9fa3fe3c41.svg(3KB)
--------b4186a7f11d640316d31f146ea79ef3f.svg(6KB)
--------216062a7dbe9fffb932503cbaf2b6fcc.svg(4KB)
--------4b0c1c1a7f0970de2545973312f21072.svg(5KB)
--------c4afd3f927cf5e7e191266f7350714e0.svg(4KB)
--------1ea7292e3e9cf1a3d9796f1e65eb291b.svg(15KB)
--------8eebf91f3af703a9133af119c2c48ce9.svg(7KB)
----approximation_ratio_finder.sage(3KB)
----brownian_probability_generator.nb(27KB)
----README.md(12KB)