Texture Mapping with Hard Constraints

We show how to continuously map a texture onto a 3D triangle mesh when some of the mesh vertices are constrained to have given ( u , v ) coordinates. This problem arises frequently in interactive texture mapping applications and, to the best of our knowledge, a complete and efficient solution is not available. Our techniques always guarantee a solution by introducing extra (Steiner) vertices in the triangulation if needed. We show how to apply our methods to texture mapping in multi-resolution scenarios and image warping and morphing.     

The Complexity of Reasoning with Global Constraints

Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.     

The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containingm_ielements of typei, 1⩽i⩽n, are the numbersF_k=∑ⁿ_i=1 m^k_i. We consider the space complexity of randomized algorithms that approximate the numbersF_k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF₀,F₁, andF₂can be approximated in logarithmic space, whereas the approximation ofF_kfork⩾6 requiresn^Ω(1)space. Applications to data bases are mentioned as well.     

Roundings Respecting Hard Constraints

A problem arising in integer linear programming is transforming a solution of a linear system to an integer one that is "close." The customary model for investigating such problems is, given a matrix A and a [0,1]-valued vector x, finding a binary vector y such that ||A(x - y)||_∞, the maximum violation of the constraints, is small. Randomized rounding and the algorithm of Beck and Fiala are ways to compute such solutions y, whereas linear discrepancy is a lower bound measure. In many applications one is looking for roundings that, in addition to being close to the original solution, satisfy some constraints without violation. The objective of this paper is to investigate such problems in a unified way. To this aim, we extend the notion of linear discrepancy to include such hard cardinality constraints. We extend the algorithm of Beck and Fiala to cope with this setting. If the constraints contain disjoint sets of variables, the rounding error increases by only a factor of two. We also show how to generate and derandomize randomized roundings respecting disjoint cardinality constraints. However, we also provide some examples showing that additional hard constraints may seriously increase the linear discrepancy. In particular, we show that the c-color linear discrepancy of a totally unimodular matrix can be as high as Ω(log c).     

Approximating the Minimum Length of Synchronizing Words Is Hard

We prove that, unless P=NP, no polynomial-time algorithm can approximate the minimum length of reset words for a given synchronizing automaton within a constant factor.     

Complexity of Clausal Constraints Over Chains

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints based on clausal patterns. A pattern abstracts away from variables and contains only information about the domain elements and the type of inequalities occurring in a constraint. Every finite set of patterns gives rise to a (clausal) constraint satisfaction problem in which all constraints in instances must have an allowed pattern. We prove that every such problem is either polynomially decidable or NP-complete, and give a polynomial-time algorithm for recognizing the tractable cases. Some of these tractable cases are new and have not been previously identified in the literature.     

On the Computational Complexity of Approximating Distributions by Probabilistic Automata

Machine Learning - We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition,...     

The Complexity of Problems for Quantified Constraints

In this paper we are interested in quantified propositional formulas in conjunctive normal form with “clauses” of arbitrary shapes. i.e., consisting of applying arbitrary relations to variables. We study the complexity of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for such formulas, both with and without a bound on the number of quantifier alternations. For each of these computational goals we get full complexity classifications: We determine the complexity of each of these problems depending on the set of relations allowed in the input formulas. Thus, on the one hand we exhibit syntactic restrictions of the original problems that are still computationally hard, and on the other hand we identify non-trivial subcases that admit efficient algorithms.     

Optimal Control of Discrete Event Systems with Weakly Hard Real-Time Constraints

We consider Discrete Event Systems that can dynamically allocate resources in order to process tasks with real-time constraints. In the case of “weakly hard” constraints, a fraction of tasks is allowed to violate them, as long as m out of any k consecutive tasks meet their respective constraints. This is a generalization of a system with purely hard real-time constraints where m = k = 1. For non-preemptive and aperiodic tasks, we formulate an optimization problem where task processing times are controlled so as to minimize a cost function while guaranteeing that a “weakly hard” criterion is satisfied. We establish a number of structural properties of the solution to this problem which lead to an efficient algorithm that does not require any explicit nonlinear programming problem solver. The low complexity of this algorithm makes it suitable for on-line applications. Simulation examples illustrate the performance improvements in such optimally controlled systems compared to ad hoc schemes.

具有模糊约束的大工业过程的关联平衡法

研究稳态大工业过程的递阶优化控制算法时,针对模型-实际存在差异以及实际约束条件有一定伸缩性的问题,将子过程模型作为等式约束,通过引入模糊系数使其转化为模糊等式约束,同时对子过程原有的不等式约束进行模糊化处理,提出具有模糊约束的关联平衡法,进而研究了两种情形(开环和有全局反馈)的关联平衡法.仿真结果表明,有全局反馈的模糊关联平衡法得到的最终解十分接近实际过程的真实最优解.     

Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data

We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family of probability distributions that represent satisfactory approximations of the complexity distribution with a dimension of the cost matrix from 20 to 49. Our main objective is to make probabilistic predictions of the complexity of individual problems for larger values of the dimension of the cost matrix. We propose a representation of the complexity distribution that makes it possible to predict the complexity. We formulate the unification hypothesis and show directions for further study, in particular proposals on the task of clustering “complex” and “simple” ATSP problems and proposals on the task of directly predicting the complexity of a specific problem instance based on the initial cost matrix.     

On the Complexity of Approximating Euclidean Traveling Salesman Tours and Minimum Spanning Trees

We consider the problems of computing r-approximate traveling salesman tours and r-approximate minimum spanning trees for a set of n points in , where d≥ 1 is a constant. In the algebraic computation tree model, the complexities of both these problems are shown to be , for all n and r such that r < n and r is larger than some constant. In the more powerful model of computation that additionally uses the floor function and random access, both problems can be solved in O(n) time if . Received January 8, 1996; revised July 15, 1996.     

干扰约束和负载均衡的无线Mesh网络网关部署策略

网关部署是无线Mesh网络规划面临的重要挑战之一.在Mesh路由器(MR)已完成部署的前提下,如何计算同时满足网络性能要求和用户流量需求的最小网关(GW)集合,已经被证明是一个NP-hard问题.文中提出了一种满足干扰约束和支持负载均衡的网关部署策略ICLB-GPS,在部署网关时消减链路干扰并实现网关负载均衡.ICLB-GPS策略综合网关选择、转发树构建和转发树间的节点迁移来完成负载均衡的网关部署,主要包含覆盖重叠和干扰消减的网关选择、基于树间节点迁移的网关负载均衡两个算法.仿真实验将ICLB-GPS算法与其它算法在网关数量、MR-GW路径长度、链路干扰程度及负载均衡指数方面进行比较,其结果表明该算法在不增加部署成本,不提高MR-GW路径长度的情况下,消减了链路干扰,实现了网关负载均衡.     

光纤通道交换机在强实时约束下的分组调度

以光纤通道交换网络强实时约束下的性能研究为背景,采用实时通信中的周期性任务模型,提出了负载匹配的加权轮循分组调度,导出了在该方法下网络消息集严格实时的充要条件,以最差情形下强实时的网络可达负载率为性能衡量指标推证了采用该算法的优越性并通过仿真进行了验证.     

硬实时系统在强分区约束下的双层分区调度

文中研究了硬实时系统在强分区约束下的双层分区的调度问题,合理建立了强分区约束下的双层分区调度模型,给出了最坏情况下的分区任务集可调度的判定条件.同时,在此基础上,提出了与分区利用率匹配的分区设计方法,导出了该方法下的系统可调度利用率的最小上限.仿真实验表明,在严格实时的条件下,文中提出的方法相对于现有方法更具优越性,并提高了分区可调度利用率的最小上限.     

Bucket Elimination: a Unifying Framework for Processing Hard and Soft Constraints

This position paper argues that extending the CSP model to a richer set of tasks such as, constraint optimization, probabilistic inference and decision theoretic tasks can be done within a unifying framework called bucket elimination. The framework allows uniform hybrids for combining elimination and conditioning guided by the problem's structure and for explicating the tradeoffs between space and time and between time and accuracy.     

基于完整约束的两轮机器人建模及平衡控制

依据完整约束下的拉格朗日方程,推导了同轴两轮移动机器人做平面直线运动时的动力学模型,并在此基础上设计了基于极点配置的状态反馈控制模型和系统数字仿真模型。结合控制模型进行了数字仿真实验研究和物理实验研究,并给出了实验分析结果。研究表明,采用基于极点配置的状态反馈控制方案,能够实现机器人动态平衡控制;机器人在初始偏角绝对值小于0.25 rad时,能够在2 s内恢复平衡,当外部干扰使机器人偏离平衡位置后,机器人能够在3 s内恢复平衡;机器人模型推导合理、有效,数字仿真和物理实验一致性好。     

Minimum k Arborescences with Bandwidth Constraints

Let $G =(V,A)$ be a digraph with source $r$. A weight function $w$ and bandwidth constraint function $b$ (positive integer) on $A$ are given. We present algorithms for finding $k$ $r$-arborescences in $G$ with minimum total weight and with bandwidth constraints.