.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
Given an undirected graph G = (V, E) and a cost vector c ∈ ℝE, the weighted girth problem is to find a circuit in G having minimum total cost. This problem is in general 𝒩𝒫-hard. A promising approach to the solution of hard combinatorial optimization problems is given by the so-called cutting plane methods. These involve linear programming techniques based on a partial description of the convex hull of the incidence vectors of possible solutions. We consider the weighted girth problem in the case where G is the complete graph Kn and study the facial structure of the circuit polytope PCn and some related polyhedra. In the appendix we give complete characterizations of PCn for n up to 6. We were motivated to study the weighted girth problem by the fact that this problem and variations of it appear as a subproblem, namely the pricing problem, in a column generation approach to the vehicle routing problem.
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息