On-line Learning and the Metrical Task System Problem

The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship between these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include: An analysis of how two recent algorithms for the MTS problem can be applied to the problem of tracking the best expert in the decision-theoretic setting, providing good bounds and an approach of a much different flavor from the well-known multiplicative-update algorithms. An analysis showing how the standard randomized Weighted Majority (or Hedge) algorithm can be used for the problem of combining on-line algorithms on-line, giving much stronger guarantees than the results of Azar, Y., Broder, A., & Manasse, M. (1993). Proc ACM-SIAM Symposium on Discrete Algorithms (pp. 432–440) when the algorithms being combined occupy a state space of bounded diameter. A generalization of the above, showing how (a simplified version of) Herbster and Warmuth's weight-sharing algorithm can be applied to give a finely competitive bound for the uniform-space Metrical Task System problem. We also give a new, simpler algorithm for tracking experts, which unfortunately does not carry over to the MTS problem.Finally, we present an experimental comparison of how these algorithms perform on a process migration problem, a problem that combines aspects of both the experts-tracking and MTS formalisms.     

Deterministic and Randomized Algorithms for Distributed On-Line Task Assignment and Load Balancing without Load Status Information

We find two interesting thresholds for the number of tasks generated under a new model of distributed on-line task assignment and load balancing environment, in which tasks are assigned without any information of current load status and load balancing is achieved together with task assignment. It is shown that balanced load distribution can be obtained deterministically when the number of tasks exceeds the first threshold. Otherwise, a simple randomized strategy can achieve balanced load distribution with high probability if the number of tasks exceeds the second threshold. Received October 30, 2000, and in revised form May 10, 2001. Online publication October 30, 2001.     

参数不确定切换系统饱和控制器的随机梯度求解方法

针对一类各子系统执行机构均具有饱和特性的参数不确定线性切换系统,首先基于公共李雅普诺夫函数法给出了任意序列下稳定的状态反馈控制器设计方法,而后构造出用于求解饱和控制律的随机梯度算法．该算法依概率可收敛到一组可行解,数值例子表明了该算法的有效性．     

Randomized Algorithms for 3-SAT

Schoning proposed a simple yet efficient randomized algorithm for solving the k-SAT problem. In the case of 3-SAT, the algorithm has an expected running time of poly(n)·(4/3)ⁿ = O(1.334ⁿ). In this paper we present randomized algorithms and show that one of them has O(1.3302ⁿ) expected running time, improving Schoning's algorithm. (Note. At this point, the fastest randomized algorithm for 3-SAT is the one given by Iwama and Tamaki that runs in O(1.324ⁿ).)     

求解随机时变背包问题的精确算法与进化算法

随机时变背包问题(RTVKP)是一种新的动态背包问题,也是一种新的动态组合优化问题,目前它的求解算法主要是动态规划的精确算法、近似算法和遗传算法.本文首先利用动态规划提出了一个求解RTVKP问题的新精确算法,对算法时间复杂度的比较结果表明:它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两个进化算法.对5个RTVKP实例的数值计算结果比较表明: 精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得的一个极好的近似解.     

Normalization-Based Task Scheduling Algorithms for Heterogeneous Multi-Cloud Environment

Cloud computing is one of the most successful technologies that offer on-demand services through the Internet. However, datacenters of the clouds may not have unlimited capacity which can fulfill the demanded services in peak hours. Therefore, scheduling workloads across multiple clouds in a federated manner has gained a significant attention in the recent years. In this paper, we present four task scheduling algorithms, called CZSN, CDSN, CDN and CNRSN for heterogeneous multi-cloud environment. The first two algorithms are based on traditional normalization techniques, namely z-score and decimal scaling respectively which are hired from data mining. The next two algorithms are based on two newly proposed normalization techniques, called distribution scaling and nearest radix scaling respectively. All the proposed algorithms are shown to work on-line. We perform rigorous experiments on the proposed algorithms using various synthetic as well as benchmark datasets. Their performances are evaluated through simulation run by measuring two performance metrics, namely makespan and average cloud utilization. The experimental results are compared with that of existing algorithms to show the efficacy of the proposed algorithms.     

面向云计算的任务调度算法综述

介绍了云计算,对任务调度在云计算中的地位做了分析,并由任务调度出发,对云计算任务调度算法的研究现状进行分类、梳理和总结.根据调度目标的不同,将算法分为单目标优化的任务调度算法和多目标的任务调度算法,对每类方法的代表性算法进行了分析介绍,并详细总结了每类方法的基本思想,对其优缺点做了分析、对比,并对改进方式进行了归纳.     

贪心算法求解k-median问题

文章讨论了用贪心算法解k-m edian问题以及其试验结果。首先提出了一个解k-m edian问题的简单贪心算法,然后对求解质量和求解的近似性能比进行了探讨。主要讨论了公制空间和非公制空间初始解的产生,用贪心算法解k-m edian问题以及全局最优解的计算。试验结果表明:贪心算法解公制空间的k-m edian问题效果要好于解非公制空间的k-m edian问题;用贪心算法解公制空间和非公制空间k-m edian问题都能得到较好的结果。     

Quantum Algorithms for Matching Problems

We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:

求解背包问题的演化算法

背包问题(Knapsack Problem, KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.本文对近十余年来利用EAs求解KP的研究情况进行一个较为详细的总结,它一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面为今后进一步利用最新提出的EAs求解KP问题提供一个可借鉴的思路.     

基于遗传算法的圆柱几何特征信息的测量

研究了各种测量圆柱信息的方法,提出了用遗传算法实现圆柱几何特征信息全局最优解的评定。对需要求的圆柱几何特征信息之间增加约束关系,减少了需要遗传算法评价的参数个数,并提高了遗传算法的收敛速度。建立了用遗传算法实现圆柱度误差最小区域法评定时目标函数数学模型的计算方法。通过实验,在给定不同的遗传算法参数下进行多次评定,该方法都能收敛到全局最优解,并计算稳定,收敛速度快,在计算机上容易实现。     

Models and Scheduling Algorithms for Mixed Data and Task Parallel Programs

An increasing number of scientific programs exhibit two forms of parallelism, often in a nested fashion. At the outer level, the application comprises coarse-grained task parallelism, with dependencies between tasks reflected by an acyclic graph. At the inner level, each node of the graph is a data-parallel operation on arrays. Designers of languages, compilers, and runtime systems are building mechanisms to support such applications by providing processor groups and array remapping capabilities. In this paper we explore how to supplement these mechanisms with policy. What properties of an application, its data size, and the parallel machine determine the maximum potential gains from using both kinds of parallelism? It turns out that large gains can be expected only for specific task graph structures. For such applications, what are practical and effective ways to allocate processors to the nodes of the task graph? In principle one could solve the NP-complete problem of finding the best possible allocation of arbitrary processor subsets to nodes in the task graph. Instead of this, our analysis and simulations show that a simpleswitchedscheduling paradigm, which alternates between pure task and pure data parallelism, provides nearly optimal performance for the task graphs considered here. Furthermore, our scheme is much simpler to implement, has less overhead than the optimal allocation, and would be attractive even if the optimal allocation was free to compute. To evaluate switching in real applications, we implemented a switching task scheduler in the parallel numerical library ScaLAPACK and used it in a nonsymmetric eigenvalue program. Even for fairly large input sizes, the efficiency improves by factors of 1.5 on the Intel Paragon and 2.5 on the IBM SP-2. The remapping and scheduling overhead is negligible, between 0.5 and 5%.     

Randomized Algorithms for Stochastic Approximation under Arbitrary Disturbances

New algorithms for stochastic approximation under input disturbance are designed. For the multidimensional case, they are simple in form, generate consistent estimates for unknown parameters under almost arbitrary disturbances, and are easily incorporated in the design of quantum devices for estimating the gradient vector of a function of several variables.     

网格任务调度策略研究

网格作为下一代Internet,具有动态性和异构性,如何有效的调度任务是影响网格成功与否的关键技术之一。首先总结了网格计算系统的体系结构和特征,分析了网格任务调度算法的基本原理和性能指标,并对各种调度策略和算法进行了分类和比较,从而为网格任务调度的研究提供了很好的参考价值。