共查询到16条相似文献,搜索用时 0 毫秒
1.
Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem 总被引:3,自引:0,他引:3
Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters
V
1
, . . ., V
k
. The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster
are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this
paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.
Received February 13, 1998; revised July 8, 1998. 相似文献
2.
3.
Consider a set of n advertisements (hereafter called ads) A ={A1,...,An} competing to be placed in a planning horizon which is divided into N time intervals called slots. An ad A
i is specified by its size s
i and frequency w
i. The size s
i represents the amount of space the ad occupies in a slot. Ad A
i is said to be scheduled if exactly w
i copies of A
i are placed in the slots subject to the restriction that a slot contains at most one copy of an ad. In this paper, we consider two problems. The MINSPACE problem minimizes the maximum fullness among all slots in a feasible schedule where the fullness of a slot is the sum of the sizes of ads assigned to the slot. For the MAXSPACE problem, in addition, we are given a common maximum fullness S for all slots. The total size of the ads placed in a slot cannot exceed S. The objective is to find a feasible schedule
of ads such that the total occupied slot space
is maximized. We examine the complexity status of both problems and provide heuristics with performance guarantees. 相似文献
4.
求解约束优化问题的粒子进化变异遗传算法 总被引:1,自引:0,他引:1
设计一种求解约束优化问题的粒子进化变异遗传算法(IGA_PSE).首先,分析候选解约束条件离差统计信息与约束违反函数之间的关系及其性质,基于约束条件离差统计信息提出一种改进约束处理方法;其次,基于粒子进化策略提出3种新变异算子;然后,讨论该算法早熟收敛的3种情况,并提出相应的种群多样化维持策略;最后,通过数值实验表明所提出的算法能够有效求解约束优化问题. 相似文献
5.
Fernando C. Gomes Cludio N. Meneses Panos M. Pardalos Gerardo Valdisio R. Viana 《Computers & Operations Research》2006,33(12):3520
Several approximation algorithms with proven performance guarantees have been proposed to find approximate solutions to classical combinatorial optimization problems. However, theoretical results may not reflect the experimental performance of the proposed algorithms. As a consequence, a question arises: how “far” from the theoretically proved performance are the experimental results? We conduct a controlled empirical study of approximation algorithms for the Vertex Cover and the Set Covering Problems. Many authors have proposed approximation algorithms for those problems. Our main goal is to better understand their strengths, weaknesses, and operation. Although we implement more than one algorithm to find feasible solutions to either problems, this work does not emphasize competition between them. The quality of the solutions related to the theoretical performance guarantees are analyzed instead. The computational experiments showed that the proven performance guarantees of all tested algorithms did not forecast well the empirical performance. 相似文献
6.
A.A. Dosiyev 《Computers & Mathematics with Applications》2018,75(5):1767-1777
The solution of the Dirichlet problem for Laplace’s equation on a special polygon is harmonically extended to a sector with the center at the singular vertex. This is followed by an integral representation of the extended function in this sector, which is approximated by the mid-point rule. By using the extension properties for the approximate values at the quadrature nodes, a well-conditioned and exponentially convergent, with respect to the number of nodes algebraic system of equations are obtained. These values determine the coefficients of the series representation of the solution around the singular vertex of the polygonal domain, which are called the generalized stress intensity factors (GSIFs). The comparison of the results with those existing in the literature, in the case of Motz’s problem, show that the obtained GSIFs are more accurate. Moreover, the extremely accurate series segment solution is obtained by taking an appropriate number of calculated GSIFs. 相似文献
7.
提出一种算法融合策略,解决单一算法求解模糊Job Shop调度问题存在的不足,提高这类问题的求解质量.算法融合策略中,采用遗传算法和蚁群算法进行并行搜索;根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力.采用算法融合策略的混合优化算法对以13个难的benchmarks问题经模糊化得到实例进行求解,在较短的时间内,得到的平均满意度较并行遗传算法(PGA)提高5.24%、较TSAB算法提高8.40% .采用算法融合策略构造的混合算法具有较强的搜索能力,说明提出的混合搜索策略是有效的. 相似文献
8.
提出了网管接口时延性能的衡量指标——网管接口操作时延的定义。对IP网中点到点的数据包传输时延进行了研究,提出了在以太网中基于ICM P的网络传输时延的测试方法,并通过实验对此方法进行了验证。将网络传输时延测试方法应用于网管接口测试的实际环境中,得到一种测试网管接口操作时延的可行方法。 相似文献
9.
随着云计算技术的广泛使用,如何对采用虚拟化技术的云计算服务器的性能进行有效管理,是云计算研究的热点问题之一.论文提出了一种基于自适应控制理论的动态资源控制策略(DRC),该控制策略在保证服务级别协议的前提下,对运行在服务器上的各个虚拟机进行优化配置,使服务器的硬件资源得到最大化的利用.同时设计了一种新型的自适应线性二次高斯控制器,来应对具有Web应用所面对的动态负载.在基于Xen技术搭建的实验平台上,对服务器的性能在不同工作负载的情况下进行了测试,并与未采用DRC策略的服务器性能进行了对比.实验结果表明,在动态工作负载下,与为采用DRC策略的服务器相比,DRC控制策略能够有效保证不同Web应用的响应时间稳定在设定的参考值. 相似文献
10.
ABSTRACTWe report on two empirical studies that explore key factors that help translate information technology governance by the board of directors into organizational performance. The first study shows that strategic alignment partially mediates the effect of board-level information technology governance on performance. The second study demonstrates that authoritarian governance style negatively moderates the effect of board-level information technology governance on performance. Together, these studies open up the black box between board-level information technology governance and organizational performance. 相似文献
11.
一种基于移动代理的网络管理系统及性能分析 总被引:16,自引:0,他引:16
当前所用的网络管理系统大都属于集中式管理模式,因此,在性能、可扩展性、灵活性等方面具有很大的局限性.基于移动代理的网络管理是针对这些不足而提出的具有潜力的解决方案之一,但是要精确地判定在什么条件下移动代理比传统的客户/服务器模式更有效是比较困难的.为此,提出了一个定量模型,从理论上分析和比较了两种结构的流量和响应时间,并就移动代理和SNMP(simple network management protocol)的性能进行了模拟实验比较.理论和实验结果都表明,当被管理的网络设备数在一定范围内时,移动代理的性能比SNMP的性能要好;对于移动代理访问固定数量的设备后再返回到网络管理器这种方案,移动代理的性能有较大的提高. 相似文献
12.
2020年伊始,新冠肺炎疫情爆发,在线教育成为疫情期间的主要教学方式。在线教育不仅是疫情面前的客观需要,也是教育的重要组成部分,是推动教育变革的重要力量。因此,文章在介绍在线教育的内涵、种类、特点的基础上,分析在线教育对教育变革的影响。以M中学为例,针对其在线教育中存在的教师信息化素养不高、师生互动少、教师对在线课堂的把控较差、学生的学习获得感不强等问题,提出了加强顶层设计、开展多种形式的教师培训、基于OBE理念进行教学设计、增强教学交互性以及降低在线学习对学生视力影响等解决策略。 相似文献
13.
In this paper, we propose a regular perturbation method to obtain approximate analytic solutions of exterior and interior Dirichlet problems for Laplace’s equation in planar domains. This method, starting from a geometrical perturbation of these planar domains, reduces our problems to a family of classical Dirichlet problems for Laplace’s equation in a circle. Numerical examples are given and comparisons are made with the solutions obtained by other approximation methods. 相似文献
14.
以某钢铁企业物流管理公司车船监控系统研发为背景,全面总结了在运输作业单跟踪和系统集成等方面取得的各项成果,分析了钢铁企业销售物流管控自动化需求,提出了由数据层、应用层和表现层构成的系统逻辑结构,以及由通讯服务器、应用服务器和数据库服务器组成的系统框架结构,给出了系统实现的主要关键技术和客户端主要功能,其中C/S客户端的... 相似文献
15.
This paper presents a new precise Hsu’s method for investigating the stability regions of the periodic motions of an undamped two-degrees-of-freedom system with cubic nonlinearity. Firstly, the incremental harmonic balance (IHB) method is used to obtain the solution of nonlinear vibration differential equations. Hsu’s method is then adopted for computing the transition matrix at the end of one period, and the precise time integration algorithm is adjusted to improve the computational precision. The stability regions of the system obtained from the precise Hsu’s, Hsu’s and improved numerical integration methods are compared and discussed. 相似文献
16.
Despite the massive body of research on the effect of media and entertainment on children’s development, especially through computer that clearly stands as the most interactive and appealing medium not only between children but also among people, the research, up to date, still lacks a true understanding of the powerful effect of the communication between children, generally all users, and the content of the entertainment. Thus, the present reflection paper was conducted towards clarifying the directions of the future research concerning the effect of media and entertainment on young children’s development based on the literature’s theoretical critiques. However, the present paper only paid attention to the most effective studies in the literature given the fact that many and many studies are just repeating what already available in the literature. The conclusion came up with two main directions of the future research on children’s development, (1) media as a quasi-human’s external regulator and (2) entertainment as a context of the learning process. Both directions yielded a new phase of learning (Self-Arousal Learning (SAL)) that the future research has to take it into account and consideration. The main topics of the SAL were stated as guidance for the main two directions of the future research. 相似文献