A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications

We present a new lower bound technique for a restricted branching program model, namely for nondeterministic graph-driven read-once branching programs (g.d.-BP1s). The technique is derived by drawing a connection between ω-nondeterministic g.d.-BP1s and ω-nondeterministic communication complexity (for the nondeterministic acceptance modes ω∈{⋁,⋀,⊕}). We apply the technique in order to prove an exponential lower bound for integer multiplication for ω-nondeterministic well-structured g.d.-BP1s. (For ω=⊕ an exponential lower bound was already obtained in [5] by using a different technique.) Further, we use the lower bound technique to prove for an explicitly defined function which can be represented by polynomial size ω-nondeterministic BP1s that it has exponential complexity in the ω-nondeterministic well-structured g.d.-BP1 model for ω∈{⋁,⊕}. This answers an open question from Brosenne et al., whether the nondeterministic BP1 model is in fact more powerful than the well-structured graph-driven variant.     

Lower Bound on the Minimum Number of Edges in Subgraphs of Johnson Graphs

Problems of Information Transmission - We prove a new lower bound on the minimum number of edges in subgraphs of Johnson graphs in the general case.     

A New Quantum Lower Bound Method,with Applications to Direct Product Theorems and Time-Space Tradeoffs

We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal. A. Ambainis supported by University of Latvia research project Y2-ZP01-100. This work conducted while at University of Waterloo, supported by NSERC, ARO, MITACS, CIFAR, CFI and IQC University Professorship. R. Špalek supported by NSF Grant CCF-0524837 and ARO Grant DAAD 19-03-1-0082. Work conducted while at CWI and the University of Amsterdam, supported by the European Commission under projects RESQ (IST-2001-37559) and QAP (IST-015848). R. de Wolf supported by a Veni grant from the Netherlands Organization for Scientific Research (NWO) and partially supported by the EU projects RESQ and QAP.     

路径和下界公式及其在调度问题中的应用

主要是研究以makespan为目标的多机器置换flow shop调度问题.由于它NP-困难,无法用多项式时间算法求解.而路径和关键路径是研究该问题的一个有力工具,对其进行深入分析可以帮助进一步理解问题最基本的特?挖掘其在更多优化算法中的应用,增加该算法的效率.在研究了原有的关键路径基础上,借助于有向栅格图和重新定义的路径及关键路径公式,直观地给出了对工件排列进行插入移动后的新排列的下界公式.另外,在遗传算法和禁忌搜索之外,还给出了下界公式在NEH启发式算法中的应用,并通过实验验证了它在排除没有希望的排列、减少有效搜索空间的强大能力.     

A New Verification Rule and Its Applications

This paper describes a verification rule for loop programs, and shows how it can be used in conjunction with the invariant-relation theorem to facilitate verification of programs.     

一种新型混合遗传算法及其应用

针对遗传算法应用的局限性,引入新的种群择优交叉运算、变异运算、遗传边界算子和相互学习过程的思想,提出一种新型混合遗传算法,提高了算法的收敛速度和稳定性,数值算例验证了该算法的有效性和实用性。     

A New Multiword Expression Metric and Its Applications

Multiword Expressions(MWEs) appear frequently and ungrammatically in natural languages.Identifying MWEs in free texts is a very challenging problem.This paper proposes a knowledge-free,unsupervised,and language-independent Multiword Expression Distance(MED).The new metric is derived from an accepted physical principle,measures the distance from an n-gram to its semantics,and outperforms other state-of-the-art methods on MWEs in two applications: question answering and named entity extraction.     

一种基于下界估计的动态表调度算法

调度是高层次综合的核心步骤之一。该文分析了常用的调度算法,并提出一种基于下界估计的动态表调度算法,实验数据表明该方法可以有效地实现多目标的优化。     

一个新的灰色综合评估模型研究

不同于一般灰数和区间灰数,本文依据灰数内涵和存在的实际背景,利用不确定性数集与普通数集(实数集)的异同点与联系,定义一种新的灰数表征方法——灰数量度.它满足四则运算法则且有自己的测度公理化定义,在此基础上建立一个灰色综合评判模型,并用案例验证它的有效性和简便性.     

一种新的位图图像编码方法及应用

论文基于对24位BMP图像文件格式的分析,提出了一种24位BMP图像按位权编码方法。实验证明,采用该方法不仅有助于提高图像的压缩比,而且可方便地实现信息的隐藏。     

The Protein Structure Prediction Problem: A Constraint Optimization Approach using a New Lower Bound

The protein structure prediction problem is one of the most (if not the most) important problem in computational biology. This problem consists of finding the conformation of a protein with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model [15], [16] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [5], [7]. We describe a constraint formulation of the HP-model structure prediction problem, and present the basic constraints and search strategy. Of course, the simple formulation would not lead to an efficient algorithm. We therefore describe redundant constraints to prune the search tree. Furthermore, we need bounding function for the energy of an HP-protein. We introduce a new lower bound based on partial knowledge about the final conformation (namely the distribution of H-monomers to layers).     

BIRCH: A New Data Clustering Algorithm and Its Applications

Data clustering is an important technique for exploratory data analysis, and has been studied for several years. It has been shown to be useful in many practical domains such as data classification and image processing. Recently, there has been a growing emphasis on exploratory analysis of very large datasets to discover useful patterns and/or correlations among attributes. This is called data mining, and data clustering is regarded as a particular branch. However existing data clustering methods do not adequately address the problem of processing large datasets with a limited amount of resources (e.g., memory and cpu cycles). So as the dataset size increases, they do not scale up well in terms of memory requirement, running time, and result quality.In this paper, an efficient and scalable data clustering method is proposed, based on a new in-memory data structure called CF-tree, which serves as an in-memory summary of the data distribution. We have implemented it in a system called BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies), and studied its performance extensively in terms of memory requirements, running time, clustering quality, stability and scalability; we also compare it with other available methods. Finally, BIRCH is applied to solve two real-life problems: one is building an iterative and interactive pixel classification tool, and the other is generating the initial codebook for image compression.     

Lower tolerance-based Branch and Bound algorithms for the ATSP

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from [23] that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances.     

恒速机上的MapReduce在线排序算法下界研究

本文研究源自于MapReduce模型系统的一类排序问题。给定两台恒速机和一批按列表到达的工件,每个工件包含两类任务:Map任务和Reduce任务。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得这批工件的最后完工时间最小。对|M_j|≥|R_j|的情形,我们证明了任意在线算法的竞争比不小于1+(1/(2s+2)).     

粗糙集理论研究的新进展

首先在粗糙集特点和优点的基础上,介绍粗糙集理论的概念和理论基础,并回顾了粗糙集理论自创建以来的发展历程。接着阐述粗糙集理论的理论研究和应用研究方向。最后,分析粗糙集理论存在的不足和缺点,并指出粗糙集理论研究的发展趋势。     

A Generalization of a Lower Bound Technique due to Fredman and Saks

{In a seminal paper of 1989, Fredman and Saks proved lower bounds for some important data-structure problems in the cell probe model. In particular, lower bounds were established on worst-case and amortized operation cost for the union-find problem and the prefix sum problem. The goal of this paper is to turn their proof technique into a general tool that can be applied to different problems and computational models. To this end we define two quantities: Output Variability depends only on the model of computation. It indicates how much variation can be found in the results of a program with certain resource bounds. This measures in some sense the power of a model. Problem Variability characterizes in a similar sense the difficulty of the problem. } Our Main Theorem shows that by comparing a model's output variability to a problem's problem variability, lower bounds on the complexity of solving the problem on the given model may be inferred. The theorem thus shows how to separate the analysis of the model of computation from that of the problem when proving lower bounds. We show how the results of Fredman and Saks fit our framework by computing the output variability of the cell probe model and the problem variability for problems considered in their paper. This allows us to reprove their lower bound results, and slightly extend them. The main purpose of this paper though is to present the generalized technique. Received January 25, 1999; revised July 30, 1999.     

A Linear Time Lower Bound on McCreight and General Updating Algorithms for Suffix Trees

Suffix trees are the fundamental data structure of combinatorial pattern matching on words. Suffix trees have been used in order to give optimal solutions to a great variety of problems on static words, but for practical situations, such as in a text editor, where the incremental changes of the text make dynamic updating of the corresponding suffix trees necessary, this data structure alone has not been used with success. We prove that, for dynamic modifications of order O(1) of words of length n, any suffix tree updating algorithm, such as the ones proposed by McCreight, requires O(n) worst-case running time, as for the full reconstruction of the suffix tree. Consequently, we argue that this data structure alone is not appropriate for the solution of combinatorial problems on words that change dynamically.     

基于色彩量化的自动配色新算法及其应用

针对印染花纹处理在电脑设计中的要求,对于一副真彩色的图样需要量化到仅有几种颜色表示,对色彩量化后的图像进行自动配色,提出了一种配色算法。配色后的图像较好地保留了原图像的轮廓特征,并且计算量较小,适于在微型计算机中实现,并已成功的应用于领带印花CAD系统中。     

向量等分量数的两方保密计算及推广应用

安全多方计算是近年来国际密码学界的研究热点.安全向量计算作为安全多方计算研究的重要内容,也是解决许多实际安全计算问题的基本工具.在科学研究中很多研究对象都可以用向量来刻画,并通过对这些向量进行各种计算从而得到所需结果,这也使安全向量计算在电子商务推荐、保密的分类、保密聚类等研究中得到了广泛应用.本文主要研究向量等分量数计算问题,即保密计算两个向量有多少个对应分量相等,这个问题的研究对于安全多方计算和隐私保护有重要的理论与实际意义.首先设计编码方法对保密向量进行编码,并结合具有加法同态性的Paillier加密方案,针对数据范围有限制和无限制两种不同情形分别设计了高效的保密计算协议,应用模拟范例严格证明了协议的安全性.作为向量等分量数保密计算协议的应用,进一步研究了向量等分量数阈值判定问题和向量优势统计问题的解决方案.并以所设计的协议为基础解决了多个点与区间(或集合)关系判定问题和字符串模式匹配等实际应用问题.复杂性分析和实验测试都表明本文协议是高效和实用的.