On the complexity of preflow-push algorithms for maximum-flow problems

We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n ² m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs inO(n ² m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n ² m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms.Research performed while the author was a Ph.D. student at Cornell University and was partially supported by the Ministry of Education of the Republic of Turkey through the scholarship program 1416.     

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.     

On the complexity of some inductive logic programming problems

The bounded ILP-consistency problem for function-free Horn clauses is described as follows. Given at setE ⁺ andE ^? of function-free ground Horn clauses and an integerk polynomial inE ⁺∪E ^?, does there exist a function-free Horn clauseC with no more thank literals such thatC subsumes each element inE ⁺ andC does not subsume any element inE ^?? It is shown that this problem is Σ ₂ ^P complete. We derive some related results on the complexity of ILP and discuss the usefulness of such complexity results.     

On the parameterized complexity of some optimization problems related to multiple-interval graphs

We show that for any constant t≥2, k-Independent Set and k-Dominating Set in t-track interval graphs are W[1]-hard. This settles an open question recently raised by Fellows, Hermelin, Rosamond, and Vialette. We also give an FPT algorithm for k-Clique in t-interval graphs, parameterized by both k and t, with running time , where n is the number of vertices in the graph. This slightly improves the previous FPT algorithm by Fellows, Hermelin, Rosamond, and Vialette. Finally, we use the W[1]-hardness of k-Independent Set in t-track interval graphs to obtain the first parameterized intractability result for a recent bioinformatics problem called Maximal Strip Recovery (MSR). We show that MSR-d is W[1]-hard for any constant d≥4 when the parameter is either the total length of the strips, or the total number of adjacencies in the strips, or the number of strips in the solution.     

The complexity of homomorphisms and renamings for minimal unsatisfiable formulas

We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F)=H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.     

On the computational complexity of bisimulation, redux

Paris Kanellakis and the second author (Smolka) were among the first to investigate the computational complexity of bisimulation, and the first and third authors (Moller and Srba) have long-established track records in the field. Smolka and Moller have also written a brief survey about the computational complexity of bisimulation [ACM Comput. Surv. 27(2) (1995) 287]. The authors believe that the special issue of Information and Computation devoted to PCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop represents an ideal opportunity for an up-to-date look at the subject.     

On the equivalence of time and frequency domain maximum likelihood estimation

Maximum likelihood estimation has a rich history. It has been successfully applied to many problems including dynamical system identification. Different approaches have been proposed in the time and frequency domains. In this paper we discuss the relationship between these approaches and we establish conditions under which the different formulations are equivalent for finite length data. A key point in this context is how initial (and final) conditions are considered and how they are introduced in the likelihood function.     

On the complexity of finding balanced oneway cuts

A bisection of an n-vertex graph is a partition of its vertices into two sets S and T, each of size n/2. The bisection cost is the number of edges connecting the two sets. In directed graphs, the cost is the number of arcs going from S to T. Finding a minimum cost bisection is NP-hard for both undirected and directed graphs. For the undirected case, an approximation of ratio O(log²n) is known. We show that directed minimum bisection is not approximable at all. More specifically, we show that it is NP-hard to tell whether there exists a directed bisection of cost 0, which we call oneway bisection. In addition, we study the complexity of the problem when some slackness in the size of S is allowed, namely, (1/2−ε)n?|S|?(1/2+ε)n. We show that the problem is solvable in polynomial time when , and provide evidence that the problem is not solvable in polynomial time when ε=o(1/(logn)⁴).     

On the query complexity of finding a local maximum point

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M?1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.     

On the VLSI complexity of some arithmetic and numerical problems

We present a survey of complexity results which arise in VLSI theory, when dealing with numerical computations. The VLSI model of computation is briefly described, and the corresponding complexity measures are presented. VLSI designs for the solution of some important arithmetic and numerical problems are also shown.     

现代智能建筑信息化工程施工中的常见问题和监理措施

近年来,伴随着社会经济、科学技术的不断进步和发展,越来越多的人开始关注居住的环境,对居住环境的要求也在逐渐的提高。在此基础上,建筑的智能化信息化成为了新的发展方向,同时智能建筑信息化工程是民用建筑工程不可分割的一部分,越来越多的人也开始留意智能建筑,在对智能建筑工程系统的施工以及设计中,可能会面临某些问题。因此,对智能建筑信息化工程施工中的控制管理是非常重要的,下面对智能建筑信息化弱电工程在施工中常见的问题以及所采取的相应监理措施简单的阐述。     

On the complexity of some colorful problems parameterized by treewidth

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.

1.

The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C_v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C_v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth.

2.

An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W[1]-hard for forests, parameterized by the number of colors on the lists.

3.

The list chromatic numberχ_l(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L_v of colors, where each list has length at least r, there is a choice of one color from each vertex list L_v yielding a proper coloring of G. We show that the problem of determining whether χ_l(G)?r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

     

MIMO雷达最大似然参数估计

多输入多输出(MIMO)雷达使用多个天线同时发射多个独立探测信号,并使用多个天线接收目标回波信号.本文考虑了发射空域分集、相干接收MIMO雷达模型及其最大似然(ML)参数估计方法.基于最大似然准则,本文推导了两种渐近最大似然算法.仿真实验的结果表明,在均匀噪声模型中,其中一种渐近算法与基于延迟求和波束形成的最大似然算法性能接近,而另一种渐近算法性能略差,但具有较低的计算复杂度.而在非均匀噪声模型中,本文所提出的两种渐近最大似然算法的性能均优于基于延迟求和波束形成的最大似然算法.     

Java-In-A-Box设计思想及在嵌入式POS公共基础模块中的应用

提出JIAB设计思想使Android适应于大规模应用程序的开发。JIAB通过对Android平台内置应用程序组件进行重新封装,使其在界面显示、业务逻辑、数据存储的权责更清晰。利用JIAB思想设计并实现了零售终端系统的公共基础模块。实践证明,JIAB思想适合在Android平台上进行大规模应用程序的开发。     

分块PCA与最大散度差鉴别分析结合的人脸识别

提出了一种将分块PCA与最大散度差鉴别分析相结合的人脸识别方法。该方法是先对原始的人脸图像进行分块,然后对分块得到的子图像矩阵采用PCA方法进行特征抽取,从而把原始模式从高维空间映射到较低维空间。接下来再对新模式采用最大散度差线性鉴别分析,这样就避免了对新模式的类内散布矩阵非奇异的要求。在ORL人脸库和Yale人脸库上分别检验了分块PCA与最大散度差鉴别分析相结合的人脸识别方法的识别性能,实验结果表明该方法抽取的鉴别特征有较强的鉴别能力。     

A granularity model for balancing the structural complexity of manufacturing systems equipment and layout

The structural complexity of a manufacturing system results primarily from the complexity of its equipment and their layout. The balance between both complexity sources can be achieved by searching for the best system granularity level, which yields a manufacturing system with the least overall structural complexity. A new system granularity complexity index is developed to sum up and normalize the complexity resulting from the system layout complexity and the equipment structural complexity. A previously developed layout complexity index together with a code-based structural complexity assessment are used to determine the structural complexity of standalone pieces of equipment and to arrive at a balance between the two sources of complexity. Cladistics analysis is used to hierarchically cluster required pieces of equipment and bundle them into more integrated equipment and machines and demonstrate the possible different system granularity levels. The new developed model is a useful tool to create specific system configuration and layout alternatives based on system components adjacency, and then select the system design with the least overall structural complexity among those alternatives. The results of the presented case study clearly demonstrated this trade-off where decomposing manufacturing systems into a highly granular configuration with standalone machines maximizes system layout complexity and minimizes equipment complexity, while at a low level of granularity pieces of equipment are bundled into complex integrated machines, lines or cells but with a very simple system layout.     

基于最大信息系数的ReliefF和支持向量机交互的自动特征选择算法

为解决特征选择ReliefF算法在利用欧氏距离选取近邻样本过程中,算法稳定性差以及选取的特征子集分类准确率低的问题,提出了一种利用最大信息系数（MIC）作为近邻样本选择标准的MICReliefF算法;同时,以支持向量机（SVM）模型的分类准确率作为评价指标,并多次寻优,以自动确定其最优特征子集,从而实现MICReliefF算法与分类模型的交互优化,即MICReliefF-SVM自动特征选择算法。在多个UCI公开数据集上对MICReliefF-SVM算法的性能进行了验证。实验结果表明,MICReliefF-SVM自动特征选择算法不仅可以筛除更多的冗余特征,而且可以选择出具有良好稳定性和泛化能力的特征子集。与随机森林（RF）、最大相关最小冗余（mRMR）、相关性特征选择（CFS）等经典的特征选择算法相比,MICReliefF-SVM算法具有更高的分类准确率。