1.0957-APPROXIMATION ALGORITHM FOR RANDOM MAX-3SAT

Wenceslas Fernandez de la Vega; Marek Karpinski

首页> 外文期刊>RAIRO Operation Research >1.0957-APPROXIMATION ALGORITHM FOR RANDOM MAX-3SAT

【24h】

1.0957-APPROXIMATION ALGORITHM FOR RANDOM MAX-3SAT

机译：1.0957-近似MAX-3SAT的近似算法

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.

机译：我们证明，在随机实例上，MAX-3SAT可以在多项式时间内以1.0957的倍数近似。

著录项

来源
《RAIRO Operation Research》 |2007年第1期|p.95-103|共9页
作者
Wenceslas Fernandez de la Vega; Marek Karpinski;
展开▼
作者单位

Department of Computer Science, Yale University;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类运筹学;
关键词
random satisfiability; approximate algorithms;

机译：随机可满足性;近似算法;
入库时间 2022-08-18 03:06:21

相似文献

外文文献
中文文献
专利

1. 9/8-Approximation Algorithm for Random MAX-3SAT [J] . W. Fernandez de la Vega, Marek Karpinski Electronic Colloquium on Computational Complexity . 2002,第126期

机译：MAX-3SAT的9/8近似算法
2. Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work [J] . Rubinstein R. Methodology and computing in applied probability . 2010,第1期

机译：带拆分的随机算法：经典随机算法为何不起作用以及如何使它们起作用
3. Randomized Monte Carlo Algorithms for Problems with Random Parameters (“Double Randomization” Method) [J] . G. A. Mikhailov Numerical analysis and applications . 2019,第2期

机译：随机蒙特卡罗算法用于随机参数的问题（“双随机化”方法）
4. Near-Optimal Large-MIMO Detection Using Randomized MCMC and Randomized Search Algorithms [C] . Kumar Ashok, Chandrasekaran Suresh, Chockalingam A., 2011 IEEE International Conference on Communications . 2011

机译：使用随机MCMC和随机搜索算法的接近最佳的大MIMO检测
5. Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs [D] . Shivram, Prakruthi. 2019

机译：遗传算法解决GPU上最大3SAT问题的遗传算法
6. Hands-On Times Adherence to Recommendations and Variance in Execution among Three Different CPR Algorithms: A Prospective Randomized Single-Blind Simulator-Based Trial [O] . Sami Rifai, Timur Sellmann, Dietmar Wetzchewald, 2020

机译：手续时间在三种不同CPR算法中遵守建议和方差：基于前瞻性的随机单盲模拟器的试验
7. 1.0957 - Approximation algorithm for Random MAX-3SAT [O] . Fernandez de La Vega Wenceslas, Karpinski Marek 2007

机译：1.0957-随机MAX-3SAT的近似算法
8. La Randomisation Permet la Construction d'Algorithmes Simples en O(N LOG* n) pourdes Problemes Lineaires Difficiles (Randomization Yields Simple O(n LOG* n) Algorithms for Difficult omega(N) Problems) [R] . Devillers, O. 1991

机译：La Randomisation permet la Construction d'algorithmes simples en O（N LOG * n）pourdes problemes Lineaires Difficiles（Randomization Yields simple O（n LOG * n）算法用于困难的欧米茄（N）问题）

1.0957-APPROXIMATION ALGORITHM FOR RANDOM MAX-3SAT

摘要

著录项

相似文献

相关主题

期刊订阅