New Bounds for Multidimensional Packing

Abstract. New upper and lower bounds are presented for a multidimensional generalization of bin packing called box packing. Several variants of this problem, including bounded space box packing, square packing, variable-sized box packing and resource augmented box packing are also studied. The main results, stated for d=2 , are as follows: a new upper bound of 2.66013 for online box packing, a new 14/9 + ɛ polynomial time offline approximation algorithm for square packing, a new upper bound of 2.43828 for online square packing, a new lower bound of 1.62176 for online square packing, a new lower bound of 2.28229 for bounded space online square packing and a new upper bound of 2.32571 for online two-sized box packing.     

Online square and cube packing

In online square packing, squares of different sizes arrive online and need to be packed into unit squares which are called bins. The goal is to minimize the number of bins used. Online cube packing is defined analogously. We show an upper bound of 2.2697 and a lower bound of 1.6406 for online square packing, and an upper bound of 2.9421 and a lower bound of 1.6680 for online cube packing. The upper bound for squares can be further reduced to 2.24437 using a computer proof. These results improve on the previously known results for the two problems. We also show improved lower bounds for higher dimensions.Preliminary versions of different parts of this paper appeared in Proc. Symp. Discr. Alg. 2004 (SODA 2004) and Proc. Eur. Symp. Alg. 2004 (ESA 2004).     

Hitting time of quantum walks with perturbation

The hitting time is the required minimum time for a Markov chain-based walk (classical or quantum) to reach a target state in the state space. We investigate the effect of the perturbation on the hitting time of a quantum walk. We obtain an upper bound for the perturbed quantum walk hitting time by applying Szegedy’s work and the perturbation bounds with Weyl’s perturbation theorem on classical matrix. Based on the definition of quantum hitting time given in MNRS algorithm, we further compute the delayed perturbed hitting time and delayed perturbed quantum hitting time (DPQHT). We show that the upper bound for DPQHT is bounded from above by the difference between the square root of the upper bound for a perturbed random walk and the square root of the lower bound for a random walk.     

Online Removable Square Packing

The online removable square packing problem is a two-dimen-sional version of the online removable Knapsack problem. For a sequence of squares with side length at most 1, we are requested to pack a subset of them into a unit square bin in an online fashion where the online player can decide whether to take the current square or not and which squares currently in the unit square to remove. The goal is to maximize the total packed area. Our results include: (i) No online algorithm can achieve a better competitive ratio than . (ii) The matching upper bound is achieved by a relatively simple online algorithm if repacking is allowed. (iii) Without repacking, we can achieve an upper bound of 3 by using the concept of bricks of Januszewski and Lassak. (iv) The offline version of the problem admits a PTAS. Research supported by NSFC (10231060).     

求解online packing problem的F-B绝对近似算法

FF算法由于其在线特性在处理在线装箱问题得到广泛使用,但它无法预测后面达到物品造成装箱率低,提出一种预留一定比例的各类未装满箱体的装箱算法。首先对未装满箱体分类并给出相应的数据结构,接着设计一种绑定配对策略来预留各类未装满箱体数目,并引入间隔函数控制新箱体的启用,最后基于FF算法结合预留策略对物品进行装箱来保证装箱的绝对近似比。提出了一种预留绑定配对策略为后续输入物品提供预测空间,特别的是F-B算法能得到5/3的绝对近似比。     

金属板材三维装箱的启发式算法

针对直方体金属板材装箱问题,提出一种模仿人装箱过程的启发式算法,该算法对木箱进行分层装箱,从最底层开始一层层往上装载,对每层出现的不平整的层进行智能填充,从而提高木箱的空间利用率,采用人工智能方法处理待装金属板材得出装箱结果,实验结果表明,该算法是行之有效的,并具有一定的通用性.     

Two-dimensional online bin packing with rotation

In two-dimensional bin packing problems, the input items are rectangles which need to be packed in a non-overlapping manner. The goal is to assign the items into unit squares using an axis-parallel packing. Most previous work on online packing concentrated on items of fixed orientation, which must be assigned such that their bottom side is parallel to the bottom of the bin. In this paper we study the case of rotatable items, which can be rotated by ninety degrees. We give almost tight bounds on the (asymptotic) competitive ratio of bounded space bin packing of rotatable items, and introduce a new unbounded space algorithm. This improves the results of Fujita and Hada.     

Lower and Upper Bounds for Linkage Discovery

For a real-valued function f defined on {0,1}n , the linkage graph of f is a hypergraph that represents the interactions among the input variables with respect to f . In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove that O(n ²logn) function evaluations are enough for bounded functions when the number of hyperedges is O(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients.     

Modified particle filter and Gaussian filter with packet dropouts

This technical note is concerned with the nonlinear filtering for networked control systems. First, the modified particle filter algorithm with intermittent observations is proposed and the conditional Cramér‐Rao lower (CRL) bound with packet dropouts for nonlinear non‐Gaussian system is derived. Second, an upper bound for the CRL bound of the Gaussian filter with packet losses is obtained by constructing a linear Gaussian‐Markovian networked system because of the complexity in direct analysis and computation. Third, a sufficient condition is given for the bounded expectation of the CRL bound, which is the necessary condition for bounded mean‐square error covariance. Finally, an example illustrates the effectiveness of the proposed filter.     

Robust estimation for discrete time‐varying systems with limited communication capacity

In this paper, we consider the state estimation problem for linear discrete time‐varying systems subject to limited communication capacity which includes measurement quantization, random transmission delay and data‐packet dropouts. Based on transforming the three communication limitations into the system with norm‐bounded uncertainties and stochastic matrices, we design a robust filter such that, for all the communication limitations, the error state of the filtering process is mean square bounded. An upper bound on the variance of the state estimation error is first found, and then, a robust filter is derived by minimizing the prescribed upper bound in the sense of the matrix norm. It is shown that the desired filter can be obtained in terms of the solutions to two Riccati‐like difference equations which also provide a recursive algorithm suitable for online computation. A simulation example is presented to demonstrate the effectiveness and applicability of the proposed algorithm. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

时变系统有限数据窗最小二乘辨识的有界收敛性

利用随机过程理论证明了有限数据窗最小二乘法的有界收敛性,给出了参数估计误差 上界的计算公式,阐述了获得最小均方参数估计误差上界时数据窗长度的选择方法.分析表明, 对于时不变随机系统,数据窗长度越大,均方参数估计误差上界越小;对于确定性时变系统,数 据窗长度越小,均方参数估计误差上界越小.因此,对于时变随机系统,一个折中方案是寻求一 个最佳数据窗长度,以使均方参数估计误差最小.该文的研究成果对于提高辨识算法的实际应 用效果有重要意义.     

Event-triggered filtering and fault estimation for nonlinear systems with stochastic sensor saturations

This paper is concerned with the filtering problem for a class of nonlinear systems with stochastic sensor saturations and event-triggered measurement transmissions. An event-triggered transmission scheme is proposed with hope to ease the traffic burden and improve the energy efficiency. The measurements are subject to randomly occurring sensor saturations governed by Bernoulli-distributed sequences. Special effort is made to obtain an upper bound of the filtering error covariance in the presence of linearisation errors, stochastic sensor saturations as well as event-triggered transmissions. A filter is designed to minimise the obtained upper bound at each time step by solving two sets of Riccati-like matrix equations, and thus the recursive algorithm is suitable for online computation. Sufficient conditions are established under which the filtering error is exponentially bounded in mean square. The applicability of the presented method is demonstrated by dealing with the fault estimation problem. An illustrative example is exploited to show the effectiveness of the proposed algorithm.     

Decision algorithms for multiplayer noncooperative games of incomplete information

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n).     

Variable Sized Online Interval Coloring with Bandwidth

We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C _a if the sum of bandwidths of intervals at each point does not exceed C _a . The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm. A preliminary version of this paper has appeared in the Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), Lecture Notes in Computer Science, Vol. 4059, pp. 29–40, Springer, 2006.     

时变系统最小均方算法的性能分析

在无过程数据平稳性假设和各态遍历等条件下,运用随机过程理论研究了最小方算法（LMS）的有界收敛性,给出了估计误差的上界,论述了LMS算法收敛因子或步长的选择方法,以使参数估计误差上界最小。这对于提高LMS算法的实际应用效果有着重要意义。LMS算法的收敛性分析表明：（1）对于确定性时不变系统,LMS算法是指数速度收敛的;（2）对于确定性时变系统,收敛因子等于1,LMS算法的参数估计误差上界最小;（3）对于时变或不变随机系统,LMS算法的参数估计误差一致有上界。     

Planar Graph Blocking for External Searching

We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance.     

Bounds on the optimal quantization performance of dynamically quantized linear systems with bounded noise

This paper studies a class of quantized linear control systems with diagonalizable system matrices and perturbed by bounded noise. The quantization performance of such systems is measured with the supremum of the quantization error sequence. Our goal is to improve this performance (reduce the quantization error) through designing appropriate quantization policies. Due to their efficiency, the dynamic quantization policies are considered in this paper. A lower bound on the optimal (minimum) quantization error is provided. We also propose a new quantization policy, whose quantization error is an upper bound on the optimal one. A more tractable upper quantization error bound is derived from the new policy. It is shown through simulations that the new policy's quantization error is very close to the lower bound, which confirms both the tightness of the lower bound and the efficiency of the new policy. The achieved lower and upper quantization error bounds, together with the quantization error of the new quantization policy, may provide a good indication on the optimal quantization performance. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Planar Graph Blocking for External Searching

Abstract. We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance.     

时变系统遗忘因子最小二乘法的有界收敛性

利用随机过程理论研究了遗忘因子最小二乘法 (FFLS)的有界收敛性, 给出了参数估计误差的上界. 分析表明: i)对于时不变确定性系统, FFLS算法产生的参数估计以指数速度收敛于真参数; ii)对于时不变随机系统, FFLS算法给出有界均方估计误差; iii)对于时变随机系统, FFLS算法可以跟踪时变参数, 且跟踪误差有界.     

Adaptive stabilization of minimum phase plant under Lipschitz uncertainty

Consideration was given to the problem of adaptive stabilization of the minimum phase plant under Lipschitz uncertainty and bounded external disturbance with unknown upper bound. The proposed adaptive stabilization algorithm is based on the recurrent set estimation of the unknown plant parameters, Lipschitz uncertainty, and the upper bound of the external disturbance and includes the online verification of the control plant model.