On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

Large buffer asymptotics for generalized processor sharing queues with Gaussian inputs

In this paper we derive large-buffer asymptotics for a two-class Generalized Processor Sharing (GPS) model. We assume both classes to have Gaussian characteristics. We distinguish three cases depending on whether the GPS weights are above or below the average rate at which traffic is sent. First, we calculate exact asymptotic upper and lower bounds, then we calculate the logarithmic asymptotics, and finally we show that the decay rates of the upper and lower bound match. We apply our results to two special Gaussian models: the integrated Gaussian process and the fractional Brownian motion. Finally we derive the logarithmic large-buffer asymptotics for the case where a Gaussian flow interacts with an on-off flow. AMS Subject Classification Primary—60K25; Secondary—68M20, 60G15     

Potential for size reduction of AlGaAs optical channel waveguide structures fabricated by focused ion beam implantation and oxidation

Optical channel waveguides formed by focused ion beam (FIB) implantation-induced mixing of AlGaAs multiple quantum well structures and subsequent oxidation of the mixed regions have the potential of significantly reducing the size of integrated photonic waveguide structures. Since FIB implantation is a direct write process characterized by nanoscale precision, we suggest its use for forming channel waveguides having nanoscale (submicrometer) widths. Calculations presented for such channel waveguides show reductions in size by at least an order of magnitude are possible for directional couplers and other structures involving curved channel waveguide sections. Such size reductions would allow the realization of significantly higher levels of device integration than are now currently possible.     

Strong and coalition-proof political equilibria under plurality and runoff rule

We analyze the effects of voter coordination on the equilibrium of voting games. Specifically, we analyze the concepts of strong equilibrium and coalition-proof equilibrium for plurality rule and runoff rule elections. We characterize these equilibria in the three candidate case, and provide results for important special cases in the general multicandidate case.      

Consensus problem in multi-agent systems with physical position neighbourhood evolving network

In multi-agent system (MAS), the communication topology of agent network plays a very important role in its consensus problem. To describe the communication topologies of MAS, a class of evolving network models with the concept of physical position neighbourhood connectivity are proposed and studied in this paper. The analysis and simulation results for network parameters such as the first nonzero eigenvalue and maximal eigenvalue of graph Laplacian matrix, clustering coefficients, average distances and degree distributions for different evolving parameters of these models are presented. The dynamical behaviour of each node on the consensus problem is also studied. It was found that the time to reach consensus becomes shorter sharply with the increasing of neighbourhood depth of the nodes in these models. And it was also found that for the maximal distance preferential attachment model (Model 3), the synthetic characteristic, such as robustness to communication delay, as well as convergence speed in consensus problem, is the best in all these models.     

Splitting graphs when calculating Myerson value for pure overhead games

A communication situation consists of a coalitional game and a graph, the nodes of the graph corresponding to the players of the game. To calculate the Myerson value for such situations, we obtain results which extend those well known for trees and cycle-complete graphs. On the other hand, in order to reduce the associated calculus for communication situations with a pure overhead game, the possibility of splitting the graph in several subgraphs is analyzed. For each fixed decomposition of the graph, a subspace of games compatible with this decomposition is given.     

采用纠缠辅助量子LDPC码和检错重传策略的 量子直传通信方案

针对现有量子信息直传协议在有噪音量子信道下传输效率低及可靠性差的问题,提出了一种有效利用纠缠资源的量子安全直传通信方案.通过收发双方共享纠缠粒子作为辅助比特,采用纠缠辅助量子低密度校验码对量子态信息进行前向纠错保护,以提高系统在噪音环境下的传输可靠性.同时采用自动请求重传策略对量子态信息进行检错编码保护,当因窃听或强噪音导致译码获得的信息不正确时,则请求发端对该组信息进行编码重传操作.文中对所选用纠缠辅助量子低密度校验码在量子退极化噪音信道下的迭代译码性能进行了仿真,最后对方案的安全性进行了分析论证.     

Using Productive Disposition to Differentiate Between Students' Level of Precision When Critiquing a Peer's Work

This study examined the productive disposition of pre‐algebra students who demonstrated similar knowledge of the focal content but varied in other academic behaviors expected in the Common Core State Standards for Mathematics (CCSSM). Specifically, the study considered students' attention to precision when critiquing a peer's work. The comprehensive definition of productive disposition used included task values (interest, utility), an ability belief (efficacy), three personal achievement goals, and negative emotions. As hypothesized, the 61 students who provided a more precise critique reported higher productive disposition (in particular, significantly higher mastery‐approach personal achievement goals and less frequent negative emotions) than the 79 students who provided a basic critique. These findings illustrate how productive disposition can inform assessments of mathematical competence within the CCSSM recently implemented across the United States.