A mildly exponential approximation algorithm for the permanent

A new approximation algorithm for the permanent of ann ×n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp(O(n ^1/2 log² n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity exp((n)).Supported by SERC Grant GR/F 90363; work done in part while visiting DIMACS (Center for Discrete Mathematics and Computer Science).Supported by an NSF PYI grant, with matching equipment grant from the AT&T Foundation; work done in part while visiting DIMACS.     

Approximate steady-state analysis of large Markov models based on the structure of their decision diagram encoding

We propose a new approximate numerical algorithm for the steady-state solution of general structured ergodic Markov models. The approximation uses a state-space encoding based on multiway decision diagrams and a transition rate encoding based on a new class of edge-valued decision diagrams. The new method retains the favorable properties of a previously proposed Kronecker-based approximation, while eliminating the need for a Kronecker-consistent model decomposition. Removing this restriction allows for a greater utilization of event locality, which facilitates the generation of both the state-space and the transition rate matrix, thus extends the applicability of this algorithm to larger and more complex models.     

Total Travel Cost in Stochastic Assignment Models

Deterministic assignment models are sometimes used to approximate properties of more complex stochastic models. One property that is of particular interest from a system optimization viewpoint is total travel cost. This paper looks at the approximation of mean total travel cost. It is shown that deterministic models will underestimate this quantity in many common situations. Furthermore, discrepancies between total travel cost under the different modelling frameworks can lead to situations in which network modifications which are detrimental according to a stochastic model appear beneficial when using the natural deterministic approximation. We conclude that estimation of mean travel cost in stochastic assignment is often best done using simulation. Some suggestions are made regarding the implementation of traffic assignment simulation.     

一种简易的无模型控制算法--改进的同时扰动随机逼近控制

同时扰动随机逼近控制算法是一种特别适合于应用在工况变化大、非线性强的工业过程的无模型控制算法。但该算法采用了神经网络作为函数逼近器，使得在工程上的实现过于复杂，文章对此作出改进，使其大大简化，更适合于在工程上应用。     

改进的最速下降法─最好点最速下降法

提出了用最速下降法解无约束多变量最优问题时，存在一些特殊点，本文称为最好点，这些最好点的负梯度方向总是直指目标函数的中心，即最优点．因此通过最好点一次迭代就能得到最优点．阐述了如何搜索得到最好的计算过程和计算程序．这个改进的最速下降法－最好点最速下降法既保持了最速下降法的优点，又消除了其锯齿现象，提高了计算速度．     

Stability preservation analysis in direct discretization of fractional order transfer functions

In this paper, a class of the direct methods for discretization of fractional order transfer functions is studied in the sense of stability preservation. The stability boundary curve is exactly determined for these discretization methods. Having this boundary helps us to recognize whether the original system and its discretized model are the same in the sense of stability. Finally, some illustrative examples are presented to evaluate achievements of the paper.     

Integration of Low-Impact Development into the International Stormwater BMP Database

Low impact development (LID) strategies are being encouraged in many communities as an approach to reduce potential adverse impacts of development on receiving streams. Many questions exist regarding how well various LID strategies perform in different settings, just as similar questions have been raised regarding performance of traditional stormwater best management practices (BMPs). Whereas historical focus on BMP performance has been water quality concentrations or loads, characterization of volume reduction benefits for both conventional and LID practices is increasingly an objective of researchers and stormwater managers. More than a decade ago, Urban Water Resources Research Council (UWRRC) members worked to develop a set of standardized monitoring and reporting protocols for traditional BMPs and to establish a master database for the purpose of evaluating BMP performance and the factors affecting performance. This effort culminated in the International Stormwater BMP Database (www.bmpdatabase.org), which contains data for more than 360 BMPs and continues to operate as a clearinghouse for stormwater BMP data and performance analyses. During 2008–2009, the International Stormwater BMP Database project expanded to better integrate LID into the database and develop a set of metrics that can be used to characterize BMP performance with regard to surface runoff volume reduction. This paper provides a condensed overview and progress report on the LID-focused effort, including the following topics: (1)?monitoring guidance for LID at the overall site development level, (2)?an overview of recent changes to the International Stormwater BMP Database to better accommodate LID studies, (3)?a summary of LID studies currently included in the database, and (4)?a proposed approach for evaluating performance of LID studies with regard to reducing surface runoff volumes.     

Real-time administration of tool sharing and best matching to enhance assembly lines balanceability and flexibility

Collaboration has been found in previous studies on the design of assembly lines to be a useful mechanism. In this study, the focus is on a collaborative assembly (CA) framework, inspired by the design principles of CCT, the Collaborative Control Theory, to improve balanceability and flexibility of assembly lines through tool sharing (TS) among idle and bottleneck workstations. TS is widely practiced in advanced assembly facilities to reduce cost and improve consistency and standardization in assembly and in assembly-and-test utilities, relying often on real time control. The framework developed here addresses the systems design aspect of Mechatronics, covering the planning, execution, and control mechanisms. Planning includes assembly line balancing (ALB) and initial TS decisions, made continually by solving a bi-objective mixed-integer program (BOMIP). A collaborative multi-agent system (CMAS) enhanced with a TS-best matching (BM) protocol is developed to execute the plan, control the process, and modify the TS decisions, considering dynamic changes in the system’s operations. Experiments show that the new CA framework significantly outperforms classic approaches (i.e., ALB without TS-BM) in terms of cycle time, utilization of tools, and balanceability. In addition, the control mechanism is proven to augment the line’s flexibility against the inherent uncertainties of assembly processes, compared to the previously developed static CA frameworks.     

Algorithm design for a class of base station location problems in sensor networks

Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1− ε) approximation algorithms for base station placement problems under any desired small error bound ε > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1/ε² complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem when the optimization objective is to maximize network capacity. Our (1− ε) approximation algorithm is the first theoretical result on this problem. Yi Shi received his B.S. degree from University of Science and Technology of China, Hefei, China, in 1998, a M.S. degree from Institute of Software, Chinese Academy of Science, Beijing, China, in 2001, and a second M.S. degree from Virginia Tech, Blacksburg, VA, in 2003, all in computer science. He is currently working toward his Ph.D. degree in electrical and computer engineering at Virginia Tech. While in undergraduate, he was a recipient of Meritorious Award in International Mathematical Contest in Modeling and 1997 and 1998, respectively. His current research focuses on algorithms and optimizations for wireless sensor networks, wireless ad hoc networks, UWB-based networks, and SDR-based networks. His work has appeared in journals and highly selective international conferences (ACM Mobicom, ACM Mobihoc, and IEEE Infocom). Y. Thomas Hou received the B.E. degree from the City College of New York in 1991, the M.S. degree from Columbia University in 1993, and the Ph.D. degree from Polytechnic University, Brooklyn, New York, in 1998, all in Electrical Engineering. Since Fall 2002, he has been an Assistant Professor at Virginia Tech, the Bradley Department of Electrical and Computer Engineering, Blacksburg, VA. His current research interests are radio resource (spectrum) management and networking for software-defined radio wireless networks, optimization and algorithm design for wireless ad hoc and sensor networks, and video communications over dynamic ad hoc networks. From 1997 to 2002, Dr. Hou was a Researcher at Fujitsu Laboratories of America, Sunnyvale, CA, where he worked on scalable architectures, protocols, and implementations for differentiated services Internet, service overlay networking, video streaming, and network bandwidth allocation policies and distributed flow control algorithms. Prof. Hou is a recipient of an Office of Naval Research (ONR) Young Investigator Award (2003) and a National Science Foundation (NSF) CAREER Award (2004). He is a Co-Chair of Technical Program Committee of the Second International Conference on Cognitive Radio Oriented Wireless Networks and Communications (CROWNCOM 2007), Orlando, FL, August 1–3, 2007. He also was the Chair of the First IEEE Workshop on Networking Technologies for Software Defined Radio Networks, September 25, 2006, Reston, VA. Prof. Hou holds two U.S. patents and has three more pending. Alon Efrat earned his Bachelor in Applied Mathematics from the Technion (Israel’s Institute of Technology) in 1991, his Master in Computer Science from the Technion in 1993, and his Ph.D in Computer Science from Tel-Aviv University in 1998. During 1998–2000 he was a Post Doctorate Research Associate at the Computer Science Department of Stanford University, and at IBM Almaden Research Center. Since 2000, he is an assistant professor at the Computer Science Department of the University of Arizona. His main research areas are Computational Geometry, and its applications to sensor networks and medical imaging.     

消除产品良率隐藏的杀手--电子束检查是铜逻辑和晶圆代工厂的最佳方法

监控和消除隐藏的电路缺陷已成为130nm和130nm以下器件的关键。这使得电子束检查正在广泛应用于开发、试生产和量产的监控过程。我们将描述当前铜逻辑和晶圆代工厂电子束检查技术的执行情况,其中包括详细的案例研究,它说明了从开发到量产过程中应用电子束检查技术的好处。我们也描述了过去克服通用工具障碍的方法。然后,分别介绍了利用电子束检查技术的新进展,以及为假设的20000WSPMφ300mm工厂模拟的最理想执行情况的最佳实例。