An approximation algorithm for the maximum cut problem and its experimental analysis

S. Bertoni; P. Campadelli; G. Grossi

首页> 外文期刊>Discrete Applied Mathematics >An approximation algorithm for the maximum cut problem and its experimental analysis

【24h】

An approximation algorithm for the maximum cut problem and its experimental analysis

机译：最大割问题的一种近似算法及其实验分析

获取原文

获取原文并翻译 | 示例

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

开具论文收录证明 >>

文献代查 >>

页面导航

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

摘要

An approximation algorithm for the maximum cut problem is designed and analyzed; its performance is experimentally compared with that of a neural algorithm and that of Goemans and Williamson's algorithm. Although the guaranteed quality of our algorithm in the worst-case analysis is poor we give experimental evidence that its average behavior is better than that of Goemans and Williamson's algorithm.

机译：设计并分析了最大割问题的近似算法。实验上将其性能与神经算法以及Goemans和Williamson算法的性能进行了比较。尽管在最坏情况分析中我们算法的保证质量很差，但我们提供了实验证据，表明其平均行为优于Goemans和Williamson算法。

著录项

来源
《Discrete Applied Mathematics》 |2001年第1期|共10页
作者
S. Bertoni; P. Campadelli; G. Grossi;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
optimization; complexity; relaxation; local search; goemans and williamson's algorithm;

机译：优化;复杂度;松弛;局部搜索;goemans和williamson算法;

相似文献

外文文献
中文文献
专利

1. An approximation algorithm for the maximum cut problem and its experimental analysis [J] . S. Bertoni, P. Campadelli, G. Grossi Discrete Applied Mathematics . 2001,第1期

机译：最大割问题的一种近似算法及其实验分析
2. Approximation algorithms for connected maximum cut and related problems [J] . Hajiaghayi MohammadTaghi, Kortsarz Guy, MacDavid Robert, Theoretical computer science . 2020,第期

机译：连接最大切割及相关问题的近似算法
3. The Maximum Congested Cut Problem and Its Robust Counterpart: Exact and Approximation Algorithms for the Single and the Multicommodity Case [J] . Maria G. Scutella Networks . 2008,第2期

机译：最大拥挤切割问题及其稳健的对立面：单商品和多商品案例的精确和近似算法
4. Approximation Algorithms for Connected Maximum Cut and Related Problems [C] . MohammadTaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Annual European symposium on algorithms . 2015

机译：连通最大割和相关问题的近似算法
5. Approximation algorithms for graph-theoretic problems: Planar subgraphs and multiway cut. [D] . Calinescu, Gruia. 1998

机译：图论问题的近似算法：平面子图和多路切割。
6. Clustering analysis of microRNA and mRNA expression data from TCGA using maximum edge-weighted matching algorithms [O] . Lizhong Ding, Zheyun Feng, Yongsheng Bai 2019

机译：使用最大边缘加权匹配算法对TCGA中microRNA和mRNA表达数据进行聚类分析
7. An approximation algorithm for the maximum cut problem and its experimental analysis [O] . Bertoni A., Campadelli P., Grossi G. 2001

机译：最大割问题的一种近似算法及其实验分析

An approximation algorithm for the maximum cut problem and its experimental analysis

摘要

著录项

相似文献

相关主题

期刊订阅