强竞赛图的强连通性

D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向图T中任意两个顶点之间恰有一条弧,则称T为竞赛图。一个强连通的竞赛图T称为强竞赛图。论文研究顶点个数大于的强竞赛图T的性质,并利用该性质给出了Moon定理的另外一种证明。     

Linear programming based approximation algorithms for feedback set problems in bipartite tournaments

We consider the feedback vertex set and feedback arc set problems on bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this result is the best that we can attain when using optimal solutions to a certain linear program as a lower bound on the optimal value. For the feedback arc set problem on bipartite tournaments, we show that a recent 4-approximation algorithm proposed by Gupta (2008) [8] is incorrect. We give an alternative 4-approximation algorithm based on an algorithm for the feedback arc set on (non-bipartite) tournaments given by van Zuylen and Williamson (2009) [14].     

基于随机演化的最小反馈弧集的改进算法

最小反馈弧集问题是一类组合优化问题,在实践中具有广泛的应用。随机演化是解决组合优化问题的一种通用的迭代随机过程。提出了一种基于随机演化的最小反馈弧集问题的改进算法。实验结果表明,改进之后的算法不仅提高了解的质量而且还减少了运行时间。     

使用粗糙集与Bayes分类器的P2P网络安全管理机制

提出一种使用粗糙集与Bayes分类器的P2P网络安全管理机制。该模型放弃了局部信任度与全局信任度等概念,对不满意事件进行分类统计,对交易节点进行分类控制。创新之处有:1)通过对节点彼此之间进行交易发生的不满意事件按照交易失败的类型、损害的严重程度、交易规模的大小等情况进行分类与量化,将交易失败事件区分为恶意攻击、大规模交易且质量不满意等类型。2)使用粗糙集分类器与Bayes分类器,将对等网络中的节点划分为可信任节点、陌生节点、恶意节点等不同的类型;建立信任节点列表与恶意节点列表;交易时将恶意节点排除在外。3)建立了反馈控制机制,使用粗糙集分类器与Bayes分类器根据节点反馈推荐的意见对被评价节点进行分类、做出评价,同时监测提出评价的节点是否有恶意行为,将反馈行为划分为诚实反馈、恶意反馈等。实验表明,与已有的安全模型相比,提出的安全管理机制对恶意行为具有更高的检测率、更满意的交易成功率以及更好的反馈信息综合能力。     

Improved FPT algorithm for feedback vertex set problem in bipartite tournament

We present an O(k³n²+n³) time FPT algorithm for the feedback vertex set problem in a bipartite tournament on n vertices with integral weights. This improves the previously best known O(k^3.12n⁴) time FPT algorithm for the problem.     

脉冲MIG焊电弧双模模糊控制

针对脉冲M IG焊焊钢时的电弧稳定性控制,采用峰值弧压反馈的方式,设计了基于修正因子的电弧双模模糊控制器,当峰值弧压偏差较大时采用基于修正因子的粗调模糊控制规则,以送丝速度Vf为控制量,而当峰值弧压偏差较小时采用基于修正因子的细调模糊控制规则,以基值时间Tb为控制量,以查表方式实现模糊控制器.最后通过试验验证了在焊接过程中弧长变化时所设计的模糊控制器可保持电弧的稳定从而保证焊接过程的稳定.     

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion

For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph’s feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters “feedback vertex set number” and “number of vertices to delete”. For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the “number of vertices to delete”. On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter “feedback edge set number”. On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter “vertex cover number and number of vertices to delete”, implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number.     

Combinatorial algorithms for feedback problems in directed graphs

Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A′⊆A such that the directed graph (V,A?A′) is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph.     

AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM

This paper proposes an enhanced Ant Colony Optimization (ACO) metaheuristic called ACO-TS to attack the minimum dominating set (MDS) problem. One of the recognized difficulties faced by ACO in its original form is premature convergence, which produces less satisfactory solutions. We propose a way to encourage a higher degree of exploration of the search space by incorporating a technique based on a concept borrowed from genetic algorithms called tournament selection. Instead of always following the standard mechanism for selecting the next solution component, an ant would make its decision based on the outcome of a tournament between randomly selected allowable components. The frequency of the tournament selection is controlled by a probability measure. The use of tournament selection is coupled with an iteration-best pheromone update. To evaluate the enhanced ACO, we consider the MDS problem formulated from ad hoc network clustering. A comparison with its original form shows that the enhanced ACO produces better solutions using fewer number of cycles. We also empirically demonstrate that the proposed ACO produces better solutions than a genetic algorithm. Finally, we argue, based on empirical results, why the tournament selection approach is preferable to a pure random selection method.     

Parameterized algorithms for feedback set problems and their duals in tournaments

The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions.     

Optimizing player earnings in professional tennis

This paper devises strategies for a professional tennis player wishing to maximize earnings. First a computer program is developed, which predicts the probability of a player reaching successive rounds in a particular tournament, and also his expected earnings. This output provides the input variables to an integer programming problem. The optimal tournament set is selected by maximizing the player's expected earnings, subject to, constraints on the maximum number of tournaments to be played, the conflicting tournaments in a given week, and the travel constraints on concurrent tours composed of various tournaments.     

基于集对分析的信任评估模型及其在服务选择中的应用

网络的大规模、异构、动态、分布和自治性造成了资源和服务的不确定性和欺骗性,从而导致服务交易双方风险增大,因此构建有效的信任模型是降低交易双方风险的重要途径。针对当前基于模糊理论的信任模型和基于反馈信息的信任评估方法存在的缺陷,提出了一种基于集对分析理论中联系数概念的主观信任表示方法,以克服模糊数学中用一个精确、唯一的隶属函数严格表示模糊概念的缺点,同时,在此模型中不是单纯基于用户的反馈信息来评价服务的信任度,而是结合服务资源在服务过程达到的服务能力来增加模型的客观性、实时性。将新的信任函数并入到传统的组件服务选择算法中,提出了两种基于信任的服务选择算法,并进行了实验仿真。结果表明,基于信任驱动的服务选择算法的任务执行成功率较传统方法有明显的提高。     

A Lagrangian approach for minimum cost single round robin tournaments

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each match and period. Since matches are carried out at one of the both opponents venues matches may be forbidden in certain periods due to unavailability of stadiums. The goal is to find a minimum cost tournament among those having no match scheduled infeasible. We employ a Lagrangian relaxation approach in order to obtain tight lower bounds. Moreover, we develop a cost-oriented repair mechanism yielding a feasible tournament schedule to each solution of the relaxed problem.     

Suboptimal feedback control of a distributed linear regulator with control and observation structure constraints†

The problem of feedback control of a linear distributed parameter system with quadratic cost where the number of control and measurement locations is finite is considered. An average cost is used to reduce the sensitivity to changes in initial conditions. A suboptimal scheme is developed to evaluate the feedback coefficients. Two examples arc solved where the feedback coefficients are evaluated in a piecewise constant form using the matrix Maximum Principle and matrix gradient.     

真空自耗电弧炉系统优化控制策略研究

为了研究真空自耗电弧炉在特殊钢冶炼过程中偏弧现象的形成原因、检测方法和改善措施,以降低产品的次品率和切除量,针对某电弧炉弧压、熔速和弧位等关键变量,设计了优化控制策略。首先,分析了真空自耗电弧炉的系统结构,基于Biot-Savart定律与数值算例,讨论了偏弧的成因;然后,研究了一种使用四个电磁传感器来检测电弧中心位置的方法;最后,基于“弧位检测—熔速与稳弧线圈修正”思想,提出了一种系统优化策略,并在MATLAB-Simulink平台上进行了仿真。仿真结果表明,偏弧现象与弧压、电流、弧长密切相关,且弧压与熔速相互耦合。因此,所提出的优化策略将弧位检测结果作为反馈量,通过弧压、熔速和稳弧线圈修正以改善偏弧是一种有效方法。     

线性单输入广义系统的镇定、极点配置和可控性*

本文利用多项式理论,讨论线性单输入广义系统在状态反馈作用下可镇定、极点配置和可控性判别等问题。     

Further results on pole-shifting using output feedback

Some previous results concerning eigenvalue assignment using constant output feedback arc extended. Necessary and sufficient conditions for an output feedback solution to exist lire shown to be equivalent to conditions imposed by the controllability and observability indices of the given system. An example is provided to illustrate the procedures described.     

磁饱和电抗器式弧焊整流器动特性的研究

磁饱和电抗器式弧焊整流器在工作时其动特性往往存在引弧冲击、飞溅、弧飘等现象,直接影响焊缝成形,进而影响焊接质量。为了提高利用该类弧焊电源焊接时的焊接质量,通过对磁饱和电抗器式弧焊整流器动特性的研究,提出了采用在焊接主回路中串联直流电感、增加交流电感、增大主变压器自身漏抗、采用电流外正反馈等方法。以使该类弧焊电源的动特性得到极大地改善。     

Eigenvalue clustering in subregions of the complex plane

Eigenvalue clustering in subregions of the complex plane is investigated for multivariable linear feedback systems. Critical constraints of all the eigenvalues of a perturbed system causing it to stay within a specified region of the nominal system arc discussed. A design procedure is developed for the selection of a parametrized class of state feedback gains for eigenvalue clustering. An illustration of the method for the case of a bounded frequency region is included.     

AdaptiviTree: adaptive tree visualization for tournament-style brackets

Online pick'em games, such as the recent NCAA college basketball March Madness tournament, form a large and rapidly growing industry. In these games, players make predictions on a tournament bracket that defines which competitors play each other and how they proceed toward a single champion. Throughout the course of the tournament, players monitor the brackets to track progress and to compare predictions made by multiple players. This is often a complex sensemaking task. The classic bracket visualization was designed for use on paper and utilizes an incrementally additive system in which the winner of each match-up is rewritten in the next round as the tournament progresses. Unfortunately, this representation requires a significant amount of space and makes it relatively difficult to get a quick overview of the tournament state since competitors take arbitrary paths through the static bracket. In this paper, we present AdaptiviTree, a novel visualization that adaptively deforms the representation of the tree and uses its shape to convey outcome information. AdaptiviTree not only provides a more compact and understandable representation, but also allows overlays that display predictions as well as other statistics. We describe results from a lab study we conducted to explore the efficacy of AdaptiviTree, as well as from a deployment of the system in a recent real-world sports tournament.