Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

Baburin AE; Della Croce F; Gimadi EK; Glazkov YV; Paschos VT

首页> 外文期刊>Discrete Applied Mathematics >Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

【24h】

Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

机译：边缘权重为1和2的2奇异销售商问题的近似算法

获取原文

获取原文并翻译 | 示例

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

开具论文收录证明 >>

文献代查 >>

页面导航

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

摘要

The NP-hard problem of finding two edge-disjoint Hamiltonian cycles of minimal total weight (also known as 2-PSPmin) in a complete (undirected) graph with edge weights 1 and 2 is considered. Polynomial lime approximation algorithms are proposed with performance ratios 5/4 (in the case of one weight function) and 11/7 (in the case of two weight functions), respectively.

机译：考虑了在具有权重1和2的完整（无向）图中找到两个总权重最小（也称为2-PSPmin）的边不相交的哈密顿循环的NP难题。提出了多项式逼近算法，其性能比分别为5/4（在一个加权函数的情况下）和11/7（在两个加权函数的情况下）。

著录项

来源
《Discrete Applied Mathematics》 |2009年第9期|共5页
作者
Baburin AE; Della Croce F; Gimadi EK; Glazkov YV; Paschos VT;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
2-peripatetic salesman problem; Approximation; Matching; Factor;

机译：二元售货员问题;逼近;匹配;因子;

相似文献

外文文献
中文文献
专利

1. Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2 [J] . Gimadi E.Kh., Glazkov Yu.V., Glebov A.N. Journal of applied and industrial mathematics . 2009,第1期

机译：在边缘权重为1和2的完整图上求解2极点推销员问题的近似算法
2. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 [J] . Baburin AE, Della Croce F, Gimadi EK, Discrete Applied Mathematics . 2009,第9期

机译：边缘权重为1和2的2奇异销售商问题的近似算法
3. Approximation algorithms for the maximum 2-peripatetic salesman problem [J] . Gimadi E.K., Ivonina E.V. Journal of applied and industrial mathematics . 2012,第3期

机译：最大2奇异推销员问题的近似算法。
4. A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem [C] . Alexander A. Ageev, Artem V. Pyatkin International Workshop on Approximation and Online Algorithms . 2008

机译：一种2近似算法，用于公制2界展示销售人员问题
5. Genetic algorithms for the traveling salesman problem using edge assembly crossovers. [D] . Seppala, Dwain Alan. 2003

机译：使用边缘组合交叉的旅行商问题遗传算法。
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. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 [O] . Baburin A.E., Della Croce F., Gimadi E.K., 2009

机译：边缘权重为1和2的2奇异销售商问题的近似算法

Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

摘要

著录项

相似文献

相关主题

期刊订阅